Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Inversions

Inversions

Time limit:1.00 s
Memory limit:512 MB

You are given a bit string, and your task is to modify it so that no adjacent bits have the same value. On each turn, you may select any bit and invert it (from 0 to 1 or from 1 to 0). What is the minimum number of inversions if you act optimally?

Input

The only input line has a bit string of length $n$.

Output

Print one integer: the minimum number of inversions.

Constraints
Example

Input:
011001

Output:
2

Explanation: You can invert the third and fourth bit, and the resulting string is 010101.