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$ баллов.