有一个小写英文字母$$$s$$$。光标位于其中一个字符上。可以通过以下操作移动光标:选择字母 $$$c$$$ 和方向(向左或向右)。然后,光标将移动到所选方向上最近出现的 $$$c$$$。如果该方向上没有字母 $$$c$$$,光标将保持在原位。例如,如果 $$$s = \mathtt{abaab}$$$ 并且光标位于第二个字符 ($$$\mathtt{a[b]aab}$$$),则:
- 向左移动到最接近的字母 $$$\mathtt{a}$$$ 将光标置于第一个字符上 ($$$\mathtt{[a]baab}$$$);
- 向右移动到最近的字母 $$$\mathtt{a}$$$ 将光标置于第三个字符 ($$$\mathtt{ab[a]ab}$$$);
- 向右移动到最近的字母 $$$\mathtt{b}$$$ 将光标放在第五个字符上 ($$$\mathtt{abaa[b]}$$$);
- 任何其他操作都会将光标留在原处。
令 $$$\mathrm{dist}(i, j)$$$ 为将光标从第 $$$i$$$ 个字符移动到第 $$$j$$$ 个字符所需的最少操作数。计算 $$$\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$$$。
输入
唯一一行包含一个非空字符串$$$s$$$,最多包含$$$10^5$$$小写英文字母。
输出
打印单个整数 $$$\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$$$。
示例
输入 #1
abcde
输出 #1
20
输入 #2
abacaba
输出 #2
58
注意
在第一个示例中,对于任何对 $$$i = j$$$,$$$\mathrm{dist}(i, j) = 0$$$,对于所有其他对,$$$1$$$。