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\le {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\le 200$
2	12	$n\le 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