Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Курсор и расстояния
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$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)$$$.

Примеры
Входные данные
abcde
Выходные данные
20
Входные данные
abacaba
Выходные данные
58
Примечание

В первом примере $$$\mathrm{dist}(i, j) = 0$$$ для любой пары $$$i = j$$$, и $$$1$$$ для всех остальных пар.