Нещодавно Козак Вус натрапив на наступну задачу.
Є рядок s. Треба знайти кількість підрядків цього рядка з такими властивостями:
Підрядок повинен мати принаймні 3 літери;
Усі літери підрядка однакові, за виключенням однієї.
Наприклад, рядки aab
, cccdc
задовільняють цим властивостям, а рядки ab
, ccc
, aabbaa
— ні.
Рядок x є підрядком рядка y, якщо x може бути отриманим видаленням кількох (можливо, жодного або всіх) символів з початку і декількох (можливо, жодного або всіх) символів з кінця.
Допоможіть Козаку Вусу розв'язувати цю задачу.
Перший рядок містить рядок s (1≤∣s∣≤2⋅105), який складається з літер латинської абетки нижнього регістру.
Виведіть єдине число — кількість підрядків з заданими умовами.
Якщо рішення працює правильно при ∣s∣≤100, то воно буде оцінюватися принаймні у 15 балів.
Якщо рішення працює правильно при ∣s∣≤5000, то воно буде оцінюватися принаймні у 40 балів.