题目描述

给定一个长度为$N$的字符串$S$。用$s_i$表示$S$的第$i$个字符。找出可以进行以下操作的最大次数。

• 选择$S$中的三个连续字符$s_i, s_{i+1}, s_{i+2} \quad (1 \leq i \leq |S|-2)$，使得$s_i = s_{i+1} \neq s_{i+2}$，然后将$s_{i+2}$替换为$s_i$。

约束条件

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

输入

输入以以下格式从标准输入给出：

$S$

输出

打印可以进行该操作的最大次数。

示例输入 1

accept

示例输出 1

3

我们可以进行三次操作，如下所示：

• 当$i=2$时，进行一次操作，将字符串更改为 acccpt；
• 当$i=3$时，进行一次操作，将字符串更改为 acccct；
• 当$i=4$时，进行一次操作，将字符串更改为 accccc。

示例输入 2

atcoder

示例输出 2

0

示例输入 3

anerroroccurred

示例输出 3

16