Description

一种求解第 $n$ 项卡特兰数的方法，是将其抽象成从二维坐标下的 $(0,0)$ 点，走到 $(n,n)$ 点的合法方案数。所谓合法方案数，要求对于某种方案的前 $k$ 步来说，向上走（即纵坐标 $+1$ ）的次数严格小于等于向右走（即横坐标 $+1$ ）的次数。

现在用 $0$ 代替向右走，用 $1$ 代替向上走，问对于给出的长度为 $2n$ 的 $01$ 串，最少需要修改多少次，才能让这种方案合法？

（修改一次，指将 $01$ 串中的某一个 $0$ 变为 $1$ 或者将某一个 $1$ 变为 $0$ 。）

Input Format

一行，一个 $01$ 串，保证其长度不超过 $10^6$ ，且长度为偶数。

Output Format

一行，一个整数，代表修改次数。

0110​

2​

Hint

将 $01$ 串修改为0101即可合法；

或者将 $01$ 串修改为0011也可合法；

显然，最少需要修改 $2$ 次