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:
The only line contains a nonempty string \(s\) of \(n \leq 10^5\) lowercase English letters.
Print a single integer \(\displaystyle \sum_{i = 1}^{n}{\sum_{j = 1}^{n}{\mathrm{dist}(i, j)}}\).
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 
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

Subtask  Score 

1  6 
2  12 
3  14 
4  18 
5  50 
6  0 