B. Хорошая тройка
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У жабы Раша есть бинарная строка $$$s$$$. Бинарная строка состоит только из нулей и единиц.

Обозначим за $$$n$$$ длину строки $$$s$$$.

Рашу нужно найти количество таких пар целых чисел $$$l$$$, $$$r$$$, что $$$1 \leq l \leq r \leq n$$$ и существует хотя бы одна такая пара целых чисел $$$x$$$, $$$k$$$, что $$$1 \leq x, k \leq n$$$, $$$l \leq x < x + 2k \leq r$$$ и $$$s_x = s_{x+k} = s_{x+2k}$$$.

Найдите это количество пар для Раша.

Входные данные

В первой строке записана строка $$$s$$$ ($$$1 \leq |s| \leq 300\,000$$$), состоящая из нулей и единиц.

Выходные данные

Выведите одно целое число: количество таких пар целых чисел $$$l$$$, $$$r$$$, что $$$1 \leq l \leq r \leq n$$$ и существует хотя бы одна такая пара целых чисел $$$x$$$, $$$k$$$, что $$$1 \leq x, k \leq n$$$, $$$l \leq x < x + 2k \leq r$$$ и $$$s_x = s_{x+k} = s_{x+2k}$$$.

Примеры
Входные данные
010101
Выходные данные
3
Входные данные
11001100
Выходные данные
0
Примечание

В первом примере есть три пары $$$l$$$, $$$r$$$, которые мы должны посчитать: $$$1$$$, $$$6$$$; $$$2$$$, $$$6$$$; $$$1$$$, $$$5$$$.

Во втором примере нет подходящей пары $$$x$$$, $$$k$$$ для исходной строки, поэтому ответ $$$0$$$.