You are given a string, $\mbox{S}$, consisting of lowercase English letters.

A string is beautiful with respect to $\mbox{S}$ if it can be derived from $\mbox{S}$ by removing exactly $2$ characters.

Find and print the number of different strings that are beautiful with respect to $\mbox{S}$.

Input Format

A single string of lowercase English letters denoting $\mbox{S}$.

Constraints

$3\leq|S|\leq10^6$
$3\leq|S|\leq20$ holds for test cases worth at least $15\%$ of the problem's score.
$3\leq|S|\leq2000$ holds for test cases worth at least $30\%$ of the problem's score.

Output Format

Print the number of different strings that are beautiful with respect to $\mbox{S}$.

Sample Input
abba

Sample Output
4

Explanation

$S=\{abba\}$ 

The following strings can be derived by removing $2$ characters from $\mbox{S}$: $ab,bb,ba,ab,ba,aa,\text{and}bb$.

This gives us our set of unique beautiful strings, $B=\{ab,ba,aa,bb\}$. As $|B|=4$, we print $4$.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import operator as op
import functools

def ncr(n, r):
	if n < r:
		return 0
	r = min(r, n - r)
	if r == 0:
		return 1
	numer = functools.reduce(op.mul, range(n, n - r, -1))
	denom = functools.reduce(op.mul, range(1, r + 1))
	return numer // denom
s = input()
s += ' '
n_blocks = 0
block_size = 0
count = 0
prev = None
prev2 = None
for c in s:
	if prev and c != prev:
		if block_size > 1:
			count += 1
		n_blocks += 1
		block_size = 1
		if c == prev2:
			count -= 1
	else:
		block_size += 1
	prev2 = prev
	prev = c
print(ncr(n_blocks, 2) + count)


s = input()
L = []
cnt = 1
i = 0
while i < len(s):
	cnt = 1
	while i + 1 < len(s) and s[i] == s[i + 1]:
		cnt += 1
		i += 1
	L.append(cnt)
	i += 1
S = [0] * len(L)
i = len(L) - 1
S[i] = L[i]
i -= 1
S.append(0)
while i > 0:
	S[i] = L[i] + S[i + 1]
	i -= 1
i = 0
dup = 0
cur_index = 0
while i < len(L):
	if L[i] == 1 and i >= 1 and (i + 1 < len(L)) and (s[cur_index - 1] == s[cur_index + 1]):
		dup += L[i] * S[i + 1] - (len(L) - i) + 1 + 1
	elif L[i] == 1 and (not (i >= 1 and i + 1 < len(L) and (s[cur_index - 1] == s[cur_index + 1]))):
		dup += L[i] * S[i + 1] - (len(L) - i) + 1
	else:
		dup += L[i] * S[i + 1] + L[i] * (L[i] - 1) / 2 - (len(L) - i)
	cur_index += L[i]
	i += 1
N = len(s)
print(int(N * (N - 1) / 2 - dup))


input_string = input()
n = len(input_string)

def exclude(s, i):
	return s[:i] + s[i + 1:]

def counts_slow(segment):
	l = len(segment)
	without_one = {exclude(segment, i) for i in range(l)}
	without_two = {exclude(x, i) for x in without_one for i in range(l - 1)}
	return (len(without_one), len(without_two))

def counts(segment):
	if len(segment) == 0:
		raise ValueError('Empty segment')
	if len(segment) == 1:
		return (1, 0)
	if len(set(segment)) == 1:
		return (1, 1)
	return counts_slow(segment)

def unequal_or_none(c1, c2):
	return c1 is None or c2 is None or c1 != c2

def get_segments(string):
	result = []
	start_index = 0
	for end_index in range(n + 1):
		if start_index == end_index:
			continue
		before2 = string[end_index - 2] if end_index - 2 in range(n) else None
		before1 = string[end_index - 1]
		after1 = string[end_index] if end_index in range(n) else None
		after2 = string[end_index + 1] if end_index + 1 in range(n) else None
		is_after1_independent = unequal_or_none(before2, after1) and unequal_or_none(before1, after1)
		is_after2_independent = unequal_or_none(before1, after2)
		is_segment_cut = is_after1_independent and is_after2_independent
		if is_segment_cut:
			segment = string[start_index:end_index]
			result.append(segment)
			start_index = end_index
	return result

def count_fast(string):
	segments = get_segments(string)
	segment_counts = [counts(segment) for segment in segments]
	counts_with_two_on_one_segment = sum([c[1] for c in segment_counts])
	different = [c[0] for c in segment_counts]
	different_sum = sum(different)
	counts_with_two_on_different_segements = sum((x * (different_sum - x) for x in different)) // 2
	return counts_with_two_on_one_segment + counts_with_two_on_different_segements
print(count_fast(input_string))


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
single = sum((x[1] == 1 for x in groups))
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


s = input()
temp = []
count = 1
new = ''
for i in range(len(s)):
	if i == 0:
		new += s[0]
	elif s[i] != s[i - 1]:
		temp += [count]
		new += s[i]
		count = 1
	else:
		count += 1
temp += [count]
d = 0
for x in temp:
	if x >= 2:
		d += 1
m = len(temp)
ans = m * (m - 1) // 2 + d
p = 0
for i in range(len(s)):
	if i + 2 <= len(s) - 1:
		if s[i] == s[i + 2] and s[i + 1] != s[i]:
			p += 1
ans -= p
print(ans)


from array import array
s = array('i', [ord(x) for x in input()])

def get_count(l):
	return round((l - 1) * l / 2)

def solve(s):
	len_s = len(s)
	max_count = get_count(len_s)
	count_before = 0
	for i in range(len(s)):
		new_count_before = count_before + 1
		if i < len_s - 1 and s[i] == s[i + 1]:
			max_count -= len_s - (i + 1) - 1
			max_count -= count_before
			new_count_before = count_before
		if i < len_s - 2 and s[i] == s[i + 2]:
			max_count -= 1
		count_before = new_count_before
	return max_count
print(solve(s))


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


def calc(A):
	ret = 0
	n = len(A)
	for i in range(n):
		(let, counter) = A[i]
		if counter > 1:
			ret += 1
			ret += n - i - 1
		else:
			ret += n - i - 1
			if i > 0 and i < n - 1 and (A[i - 1][0] == A[i + 1][0]):
				ret -= 1
	return ret

def translateString(s):
	A = []
	s.append('.')
	prev = ''
	counter = 0
	for letter in s:
		if letter != prev:
			if counter > 0:
				A.append([prev, counter])
			counter = 0
		counter += 1
		prev = letter
	return A

def main():
	s = list(input().rstrip())
	A = translateString(s)
	res = calc(A)
	print(res)
main()


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


s = input().strip()
l = len(s)
k = 0
if s[1] == s[0]:
	SN = 1
	DL = 0
else:
	SN = 0
	DL = 1
for i in range(1, l - 1):
	if s[i - 1] != s[i]:
		if s[i] == s[i + 1]:
			SN += 1
		else:
			DL += 1
			if s[i - 1] == s[i + 1]:
				k += 1
if s[l - 1] != s[l - 2]:
	DL += 1
total = DL + SN
a = total * SN - total * (total - 1) / 2 + (total - 1) * (DL - k) + (total - 2) * k
print(int(a))


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
S = input()
GroupedString = itertools.groupby(S)
m = 0
d = 0
Letters = []
Reps = []
for (k, v) in GroupedString:
	Letters.append(k)
	Reps.append(sum((1 for x in v)))
	m += 1
for i in range(0, len(Reps)):
	if Reps[i] > 1:
		d += 1
p = 0
for i in range(1, m - 1):
	if Letters[i - 1] == Letters[i + 1] and Reps[i] == 1:
		p += 1
result = m * (m - 1) / 2 + d - p
print(int(result))


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools

def get_beautiful_strings_count(s):
	groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
	multiple = sum((x[1] > 1 for x in groups))
	fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
	return multiple + len(groups) * (len(groups) - 1) // 2 - fence
s = input()
print(get_beautiful_strings_count(s))


str = input()
length = len(str)
p = 0
d = 0
m = 0
i = 0
flag = False
flag_f = False
while i < length:
	if i + 2 < length:
		if str[i] == str[i + 2] and str[i] != str[i + 1]:
			p += 1
	if i + 1 < length:
		if str[i] == str[i + 1]:
			flag = True
			if i + 2 == length:
				d += 1
		elif flag:
			m += 1
			d += 1
			flag = False
		else:
			m += 1
	else:
		m += 1
	i += 1
num = m * (m - 1) / 2 + d - p
print(int(num))


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


string = input()
groups = []
duplicate = 0
for x in string:
	idx = len(groups) - 1
	if idx >= 0 and x == groups[idx][0]:
		duplicate += 1 if groups[idx][1] == 1 else 0
		groups[idx] = (x, groups[idx][1] + 1)
	else:
		groups.append((x, 1))
meaningless = sum((groups[x - 1][0] == groups[x + 1][0] and groups[x][1] == 1 for x in range(1, len(groups) - 1)))
print(duplicate + len(groups) * (len(groups) - 1) // 2 - meaningless)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import os
import sys
import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
same_both_sides = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - same_both_sides)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import os
import sys
import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import os
import sys
import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


import itertools
s = input()
groups = [(c, sum((1 for x in l))) for (c, l) in itertools.groupby(s)]
multiple = sum((x[1] > 1 for x in groups))
fence = sum((groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 for i in range(1, len(groups) - 1)))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)