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$.

Difficulty: competition

Starter code:

Solutions:
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)


import sys
input = sys.stdin.readline

S=input().strip()
L=len(S)

ANS1=[0]*(L+10)
ANS2=[0]*(L+10)
ANS3=[0]*(L+10)

for i in range(L-2):
    if S[i]==S[i+1]==S[i+2]:
        ANS1[i]=1

for i in range(L-4):
    if S[i]==S[i+2]==S[i+4]:
        ANS2[i]=1

for i in range(L-6):
    if S[i]==S[i+3]==S[i+6]:
        ANS3[i]=1

SCORE=0

for i in range(L):
    if ANS1[i]==1:
        SCORE+=max(0,L-i-2)
    elif ANS1[i+1]==1:
        SCORE+=max(0,L-i-3)
    elif ANS1[i+2]==1:
        SCORE+=max(0,L-i-4)

    elif ANS2[i]==1:
        SCORE+=max(0,L-i-4)
    elif ANS2[i+1]==1:
        SCORE+=max(0,L-i-5)

        
    elif ANS1[i+3]==1:
        SCORE+=max(0,L-i-5)


        
        
    elif ANS1[i+4]==1:
        SCORE+=max(0,L-i-6)
    elif ANS2[i+2]==1:
        SCORE+=max(0,L-i-6)
    elif ANS3[i]==1:
        SCORE+=max(0,L-i-6)
        
    elif ANS1[i+5]==1:
        SCORE+=max(0,L-i-7)
    elif ANS2[i+3]==1:
        SCORE+=max(0,L-i-7)
    elif ANS3[i+1]==1:
        SCORE+=max(0,L-i-7)
     

    else:
        SCORE+=max(0,L-i-8)

    #print(SCORE)

print(SCORE)
        
        


from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))

s=li()
n=len(s)
total=0

def testsub(sub):
	for k in range(1,(len(sub)-1)//2+1):
			#print(k)
			if sub[0]==sub[k] and sub[k]==sub[2*k]:
				#print(len(sli))
				#print('true')				
				return True

	return False

for i in range(len(s)):
	r=n	
	lets=3
	
	done=0
	while i+lets<=len(s):
		
		sli=s[i:i+lets]
		for m in range(0,len(sli)-2):
			#print(sli[m:])
			if testsub(sli[m:]):
				done=1
				break
		if done==1:
			r=i+len(sli)-1
			break
		
		lets+=1
	#print(total,r)	
	total+=n-r


print(total)







		



s=input()
n=len(s)
sml=(n*(n+1))//2
for i in range(8):
    sml-=max(n-i,0)
good3=set()
good4=set()
good5=set()
good6=set()
good7=set()
for i in range(n-2):
    if s[i]==s[i+1]==s[i+2]:
        good3.add(i)
        sml+=1
for i in range(n-3):
    if i in good3 or i+1 in good3:
        good4.add(i)
        sml+=1
for i in range(n-4):
    if i in good4 or i+1 in good4 or s[i]==s[i+2]==s[i+4]:
        good5.add(i)
        sml+=1
for i in range(n-5):
    if i in good5 or i+1 in good5:
        good6.add(i)
        sml+=1
for i in range(n-6):
    if i in good6 or i+1 in good6 or s[i]==s[i+3]==s[i+6]:
        good7.add(i)
        sml+=1
for i in range(n-7):
    if i in good7 or i+1 in good7:
        sml+=1
print(sml)

s=input()
n=len(s)
sml=(n*(n+1))//2
for i in range(8):
    sml-=max(n-i,0)
good3=set()
good4=set()
good5=set()
good6=set()
good7=set()
for i in range(n-2):
    if s[i]==s[i+1]==s[i+2]:
        good3.add(i)
        sml+=1
for i in range(n-3):
    if i in good3 or i+1 in good3:
        good4.add(i)
        sml+=1
for i in range(n-4):
    if i in good4 or i+1 in good4 or s[i]==s[i+2]==s[i+4]:
        good5.add(i)
        sml+=1
for i in range(n-5):
    if i in good5 or i+1 in good5:
        good6.add(i)
        sml+=1
for i in range(n-6):
    if i in good6 or i+1 in good6 or s[i]==s[i+3]==s[i+6]:
        good7.add(i)
        sml+=1
for i in range(n-7):
    if i in good7 or i+1 in good7:
        sml+=1
print(sml)

s = input()

n = len(s)

ans = 0
l = 0

for i in range(0, n):
    for j in range(i - 1, l, -1):
        if 2 * j - i < l:
            break
        if s[i] == s[j] == s[j + j - i]:
             ans += ((2 * j - i) - l + 1) * (n - i)
             l = (2 * j - i + 1)	

print(ans)

from sys import stdin
s=stdin.readline().strip()
x=-1
ans=0
for i in range(len(s)):
    for j in range(1,100):
        if (i-2*j)>=0 and s[i]==s[i-j] and s[i-j]==s[i-2*j]:
            if (i-2*j)>x:
                ans+=(i-2*j-x)*(len(s)-i)
                x=i-2*j
print(ans)


s = input()
le = len(s)
m = [le] * (le + 1)
ans = 0
for i in range(le - 1, -1, -1):
    m[i] = m[i + 1]
    k = 1
    while k * 2 + i < m[i]:
        if s[i] == s[i + k] and s[i] == s[i + 2 * k]:
            m[i] = i + 2 * k
        k += 1
    ans += le - m[i]
print(ans)



def get_arr(v):
    ans = []
    while v != 0:
        ans.append(v%2)
        v//=2
    return ans[::-1]


def check_arr(arr):
    for i in range(len(arr)):
        for di in range(1, (len(arr) - i)//2 + 1):
            if i + 2 * di >=len(arr):
                continue
            if arr[i] == arr[i+di] == arr[i + 2 * di]:
                return True
    return False

s = input()


ans = (len(s) * (len(s) + 1)) // 2

for i in range(len(s)):
    for j in range(i+1, min(i + 10, len(s)+1)):
        if not check_arr(s[i:j]):
            ans-=1
print(ans)


s = input()
n = len(s)


a = [n] * (n + 1)
ans = 0

for i in range(n - 1, -1, -1):
	a[i] = a[i + 1]
	j = 1
	while i + j + j < a[i]:
		if s[i] == s[i + j] and s[i] == s[i + j + j]:
			a[i] = i + j + j
		j += 1
	ans += n - a[i]
print(ans)


s = input()
cur, ans = - 1, 0
for i in range(len(s)):
    for j in range(cur + 1, i - 1):
        if (i +  j) % 2 == 0 and s[i] == s[j] and s[i] == s[(i + j) // 2]:
            cur = j
    ans += cur + 1
print(ans)

import bisect

s = input()
n = len(s)
ans = 0
ptn = [[0]*(n+1) for i in range(4)]

for i in range(1, 5):
    for j in range(n):
        if j+2*i >= n:
            break
        if s[j] == s[j+i] and s[j+i] == s[j+2*i]:
            ptn[i-1][j+1] = 1
    for j in range(n):
        ptn[i-1][j+1] += ptn[i-1][j]
        
ans = 0
for l in range(n):
    tmp_ans = 1000000
    for i in range(4):
        tmp = bisect.bisect_left(ptn[i], ptn[i][l]+1)
        tmp_ans = min(tmp_ans, tmp-1+2*(i+1))
    ans += max(0, n - tmp_ans)
print(ans)

import bisect

s = input()
n = len(s)
ans = 0
ptn = [[0]*(n+1) for i in range(4)]

for i in range(1, 5):
    for j in range(n):
        if j+2*i >= n:
            break
        if s[j] == s[j+i] and s[j+i] == s[j+2*i]:
            ptn[i-1][j+1] = 1
    for j in range(n):
        ptn[i-1][j+1] += ptn[i-1][j]
        
ans = 0
for l in range(n):
    tmp_ans = 1000000
    for i in range(4):
        tmp = bisect.bisect_left(ptn[i], ptn[i][l]+1)
        tmp_ans = min(tmp_ans, tmp-1+2*(i+1))
    ans += max(0, n - tmp_ans)
print(ans)


s = input()
le = len(s)
m = [le] * (le + 1)
ans = 0
for i in range(le - 1, -1, -1):
    m[i] = m[i + 1]
    k = 1
    while k * 2 + i < m[i]:
        if s[i] == s[i + k] and s[i] == s[i + 2 * k]:
            m[i] = i + 2 * k
        k += 1
    ans += le - m[i]
print(ans)


import sys
import math

data = sys.stdin.read().split()
data_ptr = 0

def data_next():
    nonlocal data_ptr, data
    data_ptr += 1
    return data[data_ptr - 1]

S = data[0]
N = len(S)

ans = 0
if N >= 9:
    ans += (N - 8) * (N - 7) // 2
for l in range(3, 9):
    for i in range(N - l + 1):
        j = i + l - 1
        for start in range(i, j - 1):
            k = 1
            found = False
            while start + 2 * k <= j:
                if S[start] == S[start + k] and S[start + k] == S[start + 2 * k]:
                    found = True
                    break
                k += 1
            if found:
                ans += 1
                break
print(ans)


import sys
import math
from collections import defaultdict,deque
import heapq
s=sys.stdin.readline()[:-1]
ans=0
n=len(s)
mink=n
for i in range(n-1,-1,-1):
	k=1
	z=True
	while i+2*k<n and z:
		if s[i]==s[i+k]==s[i+2*k]:
			z=False
			continue
		k+=1
	if not z:
		mink=min(mink,i+2*k)
		#print(mink,'mink',i,'i')
	x=n-mink
	ans+=x
		#ans+=(n-(i+2*k))+(i-1)
	#print(ans,'ans',i,'i')
print(ans)

import sys
from collections import deque
#from functools import *
#from fractions import Fraction as f
#from copy import *
#from bisect import *	
#from heapq import *
#from math import gcd,ceil,sqrt
#from itertools import permutations as prm,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
di=[[-1,0],[1,0],[0,1],[0,-1]]

def string(s):
	return "".join(s)
def fori(n):
	return [fi() for i in range(n)]	
def inc(d,c,x=1):
	d[c]=d[c]+x if c in d else x
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def cil(n,m):
	return n//m+int(n%m>0)	
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<m and a[i][j]!="."
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)


t=1


while t>0:
	t-=1
	s=si()
	n=len(s)
	p=[n]*(n+1)
	ans=0
	for i in range(n):
		k=1
		while i+2*k<n:
			if s[i]==s[i+k]==s[i+2*k]:
				p[i]=i+2*k
				break
			k+=1
	for i in range(n-2,-1,-1):
		p[i]=min(p[i],p[i+1])
		ans+=(n-p[i])
	print(ans)