У жабы Раша есть бинарная строка \(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}\).
Найдите это количество пар для Раша.
Выходные данные
Выведите одно целое число: количество таких пар целых чисел \(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}\).
Примечание
В первом примере есть три пары \(l\), \(r\), которые мы должны посчитать: \(1\), \(6\); \(2\), \(6\); \(1\), \(5\).
Во втором примере нет подходящей пары \(x\), \(k\) для исходной строки, поэтому ответ \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
010101
|
3
|
|
2
|
11001100
|
0
|