Toad Rash has a binary string $s$. A binary string consists only of zeros and ones.
Let $n$ be the length of $s$.
Rash needs to find 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}$.
Find this number of pairs for Rash.
-----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}$.
-----Examples-----
Input
010101
Output
3
Input
11001100
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$.
X = [[], ['0', '1'], ['00', '01', '10', '11'], ['001', '010', '011', '100', '101', '110'], ['0010', '0011', '0100', '0101', '0110', '1001', '1010', '1011', '1100', '1101'], ['00100', '00101', '00110', '01001', '01011', '01100', '01101', '10010', '10011', '10100', '10110', '11001', '11010', '11011'], ['001001', '001011', '001100', '001101', '010010', '010011', '010110', '011001', '011010', '011011', '100100', '100101', '100110', '101001', '101100', '101101', '110010', '110011', '110100', '110110'], ['0010011', '0011001', '0011010', '0011011', '0100101', '0101100', '0101101', '0110011', '1001100', '1010010', '1010011', '1011010', '1100100', '1100101', '1100110', '1101100'], ['00110011', '01011010', '01100110', '10011001', '10100101', '11001100']]
s = input()
N = len(s)
ans = (N-1)*(N-2)//2
for i in range(N):
    for j in range(i+3, min(i+9, N+1)):
        if s[i:j] in X[j-i]:
            ans -= 1
print(ans)

X = [[], ['0', '1'], ['00', '01', '10', '11'], ['001', '010', '011', '100', '101', '110'], ['0010', '0011', '0100', '0101', '0110', '1001', '1010', '1011', '1100', '1101'], ['00100', '00101', '00110', '01001', '01011', '01100', '01101', '10010', '10011', '10100', '10110', '11001', '11010', '11011'], ['001001', '001011', '001100', '001101', '010010', '010011', '010110', '011001', '011010', '011011', '100100', '100101', '100110', '101001', '101100', '101101', '110010', '110011', '110100', '110110'], ['0010011', '0011001', '0011010', '0011011', '0100101', '0101100', '0101101', '0110011', '1001100', '1010010', '1010011', '1011010', '1100100', '1100101', '1100110', '1101100'], ['00110011', '01011010', '01100110', '10011001', '10100101', '11001100']]
s = input()
N = len(s)
ans = (N-1)*(N-2)//2
for i in range(N):
    for j in range(i+3, min(i+9, N+1)):
        if s[i:j] in X[j-i]:
            ans -= 1
print(ans)
