题目描述

给定一个长度为 $N$ 的字符串 $S$。用 $s_i$ 表示 $S$ 的第 $i$ 个字符。请你求出可以重复以下操作的最大次数。

• 选择一组连续的 $3$ 个字符 $s_i, s_{i+1}, s_{i+2}\ (1\leq i\leq |S|-2)$，满足 $s_i = s_{i+1} \neq s_{i+2}$。将 $s_{i+2}$ 替换为 $s_i$。

输入格式

输入将以以下格式从标准输入中给出。

$S$

输出格式

输出可以重复进行操作的最大次数。

样例 1

输入

accept

输出

3

样例 2

输入

atcoder

输出

0

样例 3

输入

anerroroccurred

输出

16

说明/提示

限制条件

• $3 \leq |S| \leq 2\times 10^5$
• $S$ 由小写英文字母组成

样例解释 1

可以按照如下方式进行 $3$ 次操作。

• 对 $i=2$ 进行操作。操作后的字符串为 acccpt。
• 对 $i=3$ 进行操作。操作后的字符串为 acccct。
• 对 $i=4$ 进行操作。操作后的字符串为 accccc。

由 ChatGPT 4.1 翻译