Maximum Removals in a Binary String

You are given a binary string s. You can perform an operation of removing a substring that is either \(101\) or \(010\). After each removal, the remaining parts of the string are concatenated. Your task is to return the maximum number of such removals you can perform.

Observation: Every valid removal involves a substring where the first and third characters are the same and the middle character is different. It turns out that the maximum number of removals is equal to \(\lfloor \frac{d}{2} \rfloor\), where \(d\) is the number of times consecutive characters differ in the string. In other words, if you let \[ d = \sum_{i=0}^{n-2} [s_i \neq s_{i+1}], \] then the answer is \(\lfloor d/2 \rfloor\).

For example:

• For s = "101010", there are 5 transitions so the answer is \(\lfloor5/2\rfloor = 2\).
• For s = "111000", there is only 1 transition so the answer is \(\lfloor1/2\rfloor = 0\).
• For s = "010101010", there are 8 transitions so the answer is \(\lfloor8/2\rfloor = 4\).

Your solution should read input from stdin and write the answer to stdout.

inputFormat

The input consists of a single line containing the binary string s.

outputFormat

Output a single integer representing the maximum number of removals possible.

## sample

101010

2

</p>