cursordistance

Cursor Distance

There is a string \(s\) of lowercase English letters. A cursor is positioned on one of the characters. The cursor can be moved with the following operation: choose a letter \(c\) and a direction (left or right). The cursor is then moved to the closest occurence of \(c\) in the chosen direction. If there is no letter \(c\) in that direction, the cursor stays in place. For example, if \(s = \) abaab with the cursor on the second character (a[b]aab), then:

• moving to the closest letter a to the left places the cursor on the first character ([a]baab);
• moving to the closest letter a to the right places the cursor the third character (ab[a]ab);
• moving to the closest letter b to the right places the cursor on the fifth character (abaa[b]);
• any other operation leaves the cursor in place.

Let \(\mathrm{dist}(i, j)\) be the smallest number of operations needed to move the cursor from the \(i^{th}\) character to the \(j^{th}\) character. Compute \(\displaystyle \sum_{i = 1}^{n}{\sum_{j = 1}^{n}{\mathrm{dist}(i, j)}}\).

Input format

The only line contains a non-empty string \(s\) of \(n \leq 10^5\) lowercase English letters.

Output format

Print a single integer \(\displaystyle \sum_{i = 1}^{n}{\sum_{j = 1}^{n}{\mathrm{dist}(i, j)}}\).

Limits

Subtask #	Score	Constraints
1	6	\(n \leq 200\)
2	12	\(n \leq 2000\)
3	14	\(s\) contains only letters a and b.
4	18	\(s\) contains only letters a to e.
5	50	No additional constraints

Samples

Sample Input 1	Sample Output 1
abcde	20

\(\mathrm{dist}(i, j) = 0\) for any pair \(i = j\), and \(1\) for all other pairs.

Sample Input 2	Sample Output 2
abacaba	58