Problems
G. Козак Вус та рядки
G. Козак Вус та рядки
Нещодавно Козак Вус натрапив на наступну задачу.
Є рядок $s$. Треба знайти кількість підрядків цього рядка з такими властивостями:
\begin{enumerate}
\item Підрядок повинен мати принаймні $3$ літери;
\item Усі літери підрядка однакові, за виключенням однієї.
\end{enumerate}
Наприклад, рядки \t{aab}, \t{cccdc} задовільняють цим властивостям, а рядки \t{ab}, \t{ccc}, \t{aabbaa} --- ні.
Рядок $x$ є підрядком рядка $y$, якщо $x$ може бути отриманим видаленням кількох (можливо, жодного або всіх) символів з початку і декількох (можливо, жодного або всіх) символів з кінця.
Допоможіть Козаку Вусу розв'язувати цю задачу.
\InputFile
Перший рядок містить рядок $s$ ($1 \le |s| \le 2 \cdot 10^5$), який складається з літер латинської абетки нижнього регістру.
\OutputFile
Виведіть єдине число --- кількість підрядків з заданими умовами.
\Scoring
Якщо рішення працює правильно при $|s| \le 100$, то воно буде оцінюватися принаймні у $15$ балів.
Якщо рішення працює правильно при $|s| \le 5000$, то воно буде оцінюватися принаймні у $40$ балів.
Input example #1
abcbb
Output example #1
3
Input example #2
abacabadabacaba
Output example #2
7
Input example #3
hello
Output example #3
2
Input example #4
yyyyxyyyzttt
Output example #4
21