Segmentify (Min Even-Length Subsegments)

Flip bits of an even-length binary string so that every maximal run of identical characters has even length. First minimize the number of flips; then, among all plans with the fewest flips, minimize the number of maximal runs, and output the number of runs. The single-flip explanation in the source example is incorrect; the answer is computed independently with this two-level objective.

输入格式

A single line containing an even-length binary string, 2..100000.

输出格式

Output a single integer answer.

样例 1

输入：

11100110

输出：

1

样例 2

输入：

0101

输出：

1

样例 3

输入：

001100

输出：

3

样例说明

Example 1: the four pairs are 11, 10, 01, 10; each of the last three needs 1 flip and all of them can become 11, so after the minimum 3 flips there is only 1 run; the source's 2 runs is not optimal for the secondary objective. Example 2: flipping 1 bit in each pair makes everything 0, 1 run. Example 3: the three pairs are forced to be 00, 11, 00, so 3 runs are needed.