Max Number of Operations

You are given a string s. In one operation, choose three consecutive characters s[i], s[i+1], s[i+2]; if and only if s[i]=s[i+1] and s[i+1]≠s[i+2], replace s[i+2] with s[i]. Operations can be performed in any order and any number of times; find the maximum number of operations that can be performed.

输入格式

One line containing the string s. 1≤length of s≤200000, consisting only of lowercase English letters.

输出格式

Output one integer: the maximum number of operations.

样例 1

输入：

accept

输出：

3

样例 2

输入：

aabaab

输出：

2

样例 3

输入：

aabba

输出：

4

样例说明

Example 1: in "accept", cc changes e, p, and t to c one after another, 3 times in total. Example 2: in "aabaab", first use the later aa to change the final b to a, then use the leading aa to change the 3rd character, b, to a, 2 times in total. Example 3: in "aabba", first use bb to change the final a to b, giving "aabbb", then use aa to change the three b's to a one after another, 4 times in total.