問題文

長さ $N$ の文字列 $S$ が与えられます。$S$ の $i$ 文字目を $s_i$ で表します。以下の操作を繰り返せる回数の最大値を求めてください。

• 連続する $3$ 文字 $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

以下のように $3$ 回の操作を行うことができます。

• $i=2$ に対して操作を行う。操作後の文字列は acccpt になる。
• $i=3$ に対して操作を行う。操作後の文字列は acccct になる。
• $i=4$ に対して操作を行う。操作後の文字列は accccc になる。

入力例 2

atcoder

出力例 2

0

入力例 3

anerroroccurred

出力例 3

16