Дана строка \(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)\).
Выходные данные
Выведите одно число \(\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)\).
Примечание
В первом примере \(\mathrm{dist}(i, j) = 0\) для любой пары \(i = j\), и \(1\) для всех остальных пар.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abcde
|
20
|
|
2
|
abacaba
|
58
|