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: HARD
Tags: Amortized analysis

Complete search
Skill types: Amortized analysis

Complete search

Starter code:

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


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)


import sys
from collections import deque

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
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)


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)


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)


from collections import defaultdict as dd
import math

def nn():
	return int(input())

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

def mi():
	return 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):
		if sub[0] == sub[k] and sub[k] == sub[2 * k]:
			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):
			if testsub(sli[m:]):
				done = 1
				break
		if done == 1:
			r = i + len(sli) - 1
			break
		lets += 1
	total += n - r
print(total)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
s = input()
ma = -1
n = len(s)
one = []
two = []
ans = 0
for i in range(n):
	if s[i] == '1':
		cou = -1
		t = -9
		while True:
			if cou == -len(one) or len(one) == 0:
				break
			e = one[cou]
			dif = i - one[cou]
			if one[cou] - dif >= 0 and s[one[cou] - dif] == '1':
				t = one[cou] - dif
				break
			elif one[cou] - dif < 0:
				break
			cou -= 1
		if t < ma:
			one.append(i)
			continue
		else:
			ans += (t - ma) * (n - i)
			ma = max(ma, t)
		one.append(i)
	else:
		cou = -1
		t = -9
		while True:
			if cou == -len(two) or len(two) == 0:
				break
			e = two[cou]
			dif = i - two[cou]
			if two[cou] - dif >= 0 and s[two[cou] - dif] == '0':
				t = two[cou] - dif
				break
			elif two[cou] - dif < 0:
				break
			cou -= 1
		if t < ma:
			two.append(i)
			continue
		else:
			ans += (t - ma) * (n - i)
			ma = max(ma, t)
		two.append(i)
print(ans)


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)


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)


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)
	x = n - mink
	ans += x
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 k > 20:
					break
				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)


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)


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


import os
import sys
from io import BytesIO, IOBase

def main():
	arr = list(map(int, input()))
	n = len(arr)
	ans = 0

	def solve(z):
		zz = min(n, z + 10)
		for k in range(z + 2, zz):
			for j in range(z, k):
				if not k + j & 1 and arr[j] == arr[k] == arr[(k + j) // 2]:
					return (j, n - k)
		return (-1, 0)
	i = 0
	while i < n:
		(l, r) = solve(i)
		if l == -1:
			break
		ans += (l - i + 1) * r
		i = l + 1
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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()
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)


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()

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)


import os, sys
from io import BytesIO, IOBase

def main():
	s = input().strip()
	n = len(s)
	(ans, maxi) = (0, n)
	for i in range(n - 1, -1, -1):
		for j in range(i + 2, maxi, 2):
			if s[i] == s[j] == s[(i + j) // 2]:
				maxi = j
				break
		ans += n - maxi
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(50001)]
pp = []

def SieveOfEratosthenes(n=50000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for i in range(50001):
		if prime[i]:
			pp.append(i)
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 os
import sys
from io import BytesIO, IOBase

def main():
	b = set()
	for l in range(3, 10):
		for i in range(pow(2, l)):
			z = bin(i)[2:].zfill(l)
			lz = len(z)
			for j in range(lz):
				(k, f) = (1, 0)
				while j + 2 * k < lz:
					if z[j] == z[j + k] == z[j + 2 * k]:
						b.add(z)
						f = 1
						break
					k += 1
				if f:
					break
	s = input().rstrip()
	n = len(s)
	ans = n * (n + 1) // 2
	for i in range(n):
		for j in range(i + 3, min(i + 9, n + 1)):
			if s[i:j] in b:
				z = j - i - 1
				ans -= z
				break
		else:
			j = min(n, i + 8)
			z = j - i
			ans -= z
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def func(st, en):
	for i in range(st, en + 1):
		for j in range(i + 1, en + 1):
			if (j - i + 1) % 2 == 1:
				if s[(i + j) // 2] == s[i] == s[j]:
					return False
	return True
s = input().strip()
c = 0
n = len(s)
for i in range(2, 9):
	for j in range(len(s)):
		if i + j < len(s):
			if func(j, j + i):
				c += 1
print(n * (n + 1) // 2 - c - n - n + 1)


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)


import sys
import math
import collections
import heapq
input = sys.stdin.readline
s = input()
n = len(s) - 1
if n < 3:
	print(0)
else:
	c = 0
	l = [n] * (n + 1)
	for i in range(n - 1, -1, -1):
		l[i] = l[i + 1]
		k = 1
		while i + 2 * k < l[i]:
			if s[i] == s[i + k] == s[i + 2 * k]:
				l[i] = i + 2 * k
			k += 1
		c += n - l[i]
	print(c)


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)


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)


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)


import sys
input = sys.stdin.readline
s = list(input().rstrip())
n = len(s)
for i in range(n):
	s[i] = int(s[i])
ans = n * (n - 1) // 2
if n >= 2:
	ans -= n - 1
for d in range(3, 13):
	for i in range(n):
		if i + d > n:
			break
		s1 = s[i:i + d]
		flg = False
		for k in range(1, 5):
			for st in range(d):
				if st + 2 * k >= d:
					break
				if s1[st] == s1[st + k] == s1[st + 2 * k]:
					flg = True
					break
		if not flg:
			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)