Good Triple

Description:

Input:

The first line contains the string $$$s$$$ ($$$1 \leq |s| \leq 300\,000$$$), consisting of zeros and ones.

Output:

Output one integer: the number of such pairs of integers $$$l$$$, $$$r$$$ that $$$1 \leq l \leq r \leq n$$$ and there is at least one pair of integers $$$x$$$, $$$k$$$ such that $$$1 \leq x, k \leq n$$$, $$$l \leq x < x + 2k \leq r$$$, and $$$s_x = s_{x+k} = s_{x+2k}$$$.

Sample Input:

010101

Sample Output:

3

Sample Input:

11001100

Sample Output:

0

Note:

In the first example, there are three $$$l$$$, $$$r$$$ pairs we need to count: $$$1$$$, $$$6$$$; $$$2$$$, $$$6$$$; and $$$1$$$, $$$5$$$.

In the second example, there are no values $$$x$$$, $$$k$$$ for the initial string, so the answer is $$$0$$$.