Find Minimum Inefficienty

Replace each ? independently with 0 or 1 to minimize the number of adjacent character pairs that differ. Fixed 0/1 characters cannot be changed.

输入格式

One line containing a string made only of 0, 1 and ?. The complete original bounds are 1≤length≤100000.

输出格式

Output a single integer, the answer.

样例 1

输入：

??011??0

输出：

2

样例 2

输入：

00?10??1?

输出：

3

样例 3

输入：

???

输出：

0

样例说明

The answers are 2, 3 and 0. The explanation of the original second example gives 10 characters, which does not match the 9-character input; a valid optimal filling, 001101111, has length 9 and 3 changes.