Convert to Good String

You are given a string s containing only 0 and 1. A string is called good if it contains neither the subsequence "010" nor the subsequence "101" (subsequences need not be contiguous). Each operation changes one 0 to 1 or one 1 to 0. Find the minimum number of operations needed to turn s into a good string.

输入格式

One line with a 01 string s. 1≤(length of s)≤10^6.

输出格式

Output one integer, the minimum number of operations.

样例 1

输入：

111101110100

输出：

2

样例 2

输入：

01010

输出：

2

样例 3

输入：

1100

输出：

0

样例说明

Example 1: s="111101110100"; changing the 0s at positions 5 and 9 (1-indexed) to 1 gives "111111111100", 2 operations in total. Example 2: "01010" can become "00000" or "01111", among others, needing at least 2 operations. Example 3: "1100" is already good, so the answer is 0.