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 ≤ l ≤ r ≤ n and there is at least one pair of integers x, k such that 1 ≤ x, k ≤ n, l ≤ x < x + 2k ≤ 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 ≤ |s| ≤ 300 000), consisting of zeros and ones.

Output

Output one integer: the number of such pairs of integers l, r that 1 ≤ l ≤ r ≤ n and there is at least one pair of integers x, k such that 1 ≤ x, k ≤ n, l ≤ x < x + 2k ≤ 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: HARD
Tags: Amortized analysis

Complete search
Skill types: Amortized analysis

Complete search

Starter code:

Solutions:
from sys import stdin
s = stdin.readline().strip()
x = -1
ans = 0
for i in range(len(s)):
	for j in range(1, 10):
		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()

def pri(l, r):
	k = 1
	while r - 2 * k >= l:
		if s[r] != s[r - k] or s[r - k] != s[r - 2 * k]:
			k += 1
			continue
		return False
	return True
ans = 0
for i in range(len(s)):
	j = i
	while j < len(s) and pri(i, j):
		j += 1
	ans += len(s) - j
print(ans)


def good(l, r):
	for x in range(l, r):
		for k in range(1, 10):
			if x + (k << 1) <= r:
				if s[x] == s[x + k] and s[x + k] == s[x + (k << 1)]:
					return False
			else:
				break
	return True
s = input()
n = len(s)
answer = 0
for l in range(n):
	r = l
	while good(l, r):
		r += 1
		if r >= n:
			break
	answer += n - r
print(answer)


import sys
data_string = input()
total_seq = 0
current_end_seq = 0
step = 0
while step < len(data_string) - 1:
	step += 1
	total_seq = total_seq + current_end_seq
	min_d = 1
	while step - 2 * min_d + 1 > current_end_seq:
		if data_string[step] == data_string[step - min_d] == data_string[step - 2 * min_d]:
			current_end_seq = step - 2 * min_d + 1
			break
		min_d += 1
print(total_seq + current_end_seq)


s = input()
n = len(s)
ans = 0
X = []
for x in range(n):
	k = 1
	while x + 2 * k < n and (s[x] != s[x + k] or s[x] != s[x + 2 * k]):
		k += 1
	if x + 2 * k < n:
		X += [(x, x + 2 * k)]
for i in range(len(X) - 2, -1, -1):
	X[i] = (X[i][0], min(X[i][1], X[i + 1][1]))
I = 0
if len(X):
	for l in range(n):
		if X[I][0] < l:
			while I < len(X) and X[I][0] < l:
				I += 1
			if I == len(X):
				break
		ans += max(0, n - X[I][1])
print(ans)


def parse(c, n):
	l = [-1] * n
	for x in c:
		se = set(x)
		for i in range(len(x) - 1):
			for j in range(i + 1, len(x)):
				k = x[j] - x[i]
				if x[i] + k + k >= n:
					break
				if x[i] + k + k in se:
					l[x[i] + k + k] = x[i]
					break
	res = 0
	prex = -1
	for i in range(n):
		if l[i] <= prex:
			continue
		res = res + (l[i] - prex) * (n - i)
		prex = l[i]
	return res
s = input()
one = [i for i in range(len(s)) if s[i] == '1']
zero = [i for i in range(len(s)) if s[i] == '0']
ans = parse((one, zero), len(s))
print(ans)


import sys
S = sys.stdin.readline()
S = S.strip()
n = len(S)
ans = 0

def check(i, j):
	if j - i < 3:
		return False
	for x in range(i, j):
		for k in range(1, j - i):
			if x + 2 * k >= j:
				break
			if S[x] == S[x + k] == S[x + 2 * k]:
				return True
	return False
for i in range(n):
	for j in range(i + 1, min(i + 100, n + 1)):
		if check(i, j):
			ans += n - j + 1
			break
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)


s = input()
len = len(s)
r = len
ans = 0
for l in range(len)[::-1]:
	r = min(r, l + 9)
	k = 1
	while l + 2 * k < r:
		if s[l] == s[l + k] and s[l] == s[l + 2 * k]:
			r = min(r, l + 2 * k)
			break
		k += 1
	ans += len - r
print(ans)


from math import *
from collections import *
import sys
sys.setrecursionlimit(10 ** 9)
s = input()
n = len(s)
ans = 0
for i in range(n):
	m = 10 ** 6
	for k in range(1, 5):
		for j in range(i, i + 7):
			if j + 2 * k >= n:
				break
			if s[j] == s[j + k] and s[j] == s[j + 2 * k]:
				m = min(m, j + 2 * k)
	if m != 10 ** 6:
		ans += n - m
print(ans)


s = input()
n = len(s)
l = 0
ans = 0
for i in range(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)