Cursor Distance
Description
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 = \mathtt{abaab}$ with the cursor on the second character ($\mathtt{a[b]aab}$), then:
- moving to the closest letter $\mathtt{a}$ to the left places the cursor on the first character ($\mathtt{[a]baab}$);
- moving to the closest letter $\mathtt{a}$ to the right places the cursor the third character ($\mathtt{ab[a]ab}$);
- moving to the closest letter $\mathtt{b}$ to the right places the cursor on the fifth character ($\mathtt{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)$.
The only line contains a non-empty string $s$ of at most $10^5$ lowercase English letters.
Print a single integer $\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$.
Input
The only line contains a non-empty string $s$ of at most $10^5$ lowercase English letters.
Output
Print a single integer $\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$.
Samples
abcde
20
abacaba
58
Note
In the first sample case, $\mathrm{dist}(i, j) = 0$ for any pair $i = j$, and $1$ for all other pairs.