题目描述

给定一个长度为 $n$ 的 $01$ 字符串。

你可以删除最左边若干个字符，也可以删除最右边若干个字符，两边删除的数量都可以为 $0$，也允许把整个字符串删空。

最终剩下的部分是原字符串的一个连续子串，也可能为空串

设删掉的字符中 1 的个数为 $A$，剩下子串中 0 的个数为 $B$。请最小化 $\max(A,B)$。

输入格式

一行一个只包含 0 和 1 的字符串。

输出格式

输出一个整数，表示 $\max(A,B)$ 的最小值。

样例

1001001001001

3

111011001000

1

0101

1

样例解释

样例 1 中，可以保留子串 1001。原串中共有 $5$ 个 1，保留了其中 $2$ 个，因此删掉的 1 有 $A=3$；保留子串中有 $2$ 个 0，因此 $B=2$。此时 $\max(A,B)=3$，可以证明不存在更优方案。

样例 2 中，可以保留子串 111011。删掉的 1 有 $1$ 个、剩下的 0 有 $1$ 个，因此 $\max(1,1)=1$。

样例 3 中，可以保留子串 1。此时删掉的 1 有 $1$ 个，剩下的 0 有 $0$ 个，因此 $\max(1,0)=1$。

数据范围与约定

对于 $100\%$ 的数据，字符串只包含 0 和 1。