G. Козак Вус та рядки

Нещодавно Козак Вус натрапив на наступну задачу.

Є рядок $s$. Треба знайти кількість підрядків цього рядка з такими властивостями:

1. Підрядок повинен мати принаймні $3$ літери;

2. Усі літери підрядка однакові, за виключенням однієї.

Наприклад, рядки aab, cccdc задовільняють цим властивостям, а рядки ab, ccc, aabbaa — ні.

Рядок $x$ є підрядком рядка $y$, якщо $x$ може бути отриманим видаленням кількох (можливо, жодного або всіх) символів з початку і декількох (можливо, жодного або всіх) символів з кінця.

Допоможіть Козаку Вусу розв'язувати цю задачу.

Вхідні дані

Перший рядок містить рядок $s$ ($1\le |s|\le 2\cdot 10^5$), який складається з літер латинської абетки нижнього регістру.

Вихідні дані

Виведіть єдине число — кількість підрядків з заданими умовами.

Приклади

Оцінювання

Якщо рішення працює правильно при $|s|\le 100$, то воно буде оцінюватися принаймні у $15$ балів.

Якщо рішення працює правильно при $|s|\le 5000$, то воно буде оцінюватися принаймні у $40$ балів.