题目描述

我们称一个字符串是一个 01串，当且仅当它仅由字符 '0' 和 '1' 构成。

现在给你一个 01串 $s$。

你可以从字符串的开头连续删除一些字符，同时在字符串的结尾连续删除一些字符。（当然，你也可以不删除开头的连续字符，也可以不删除结尾的连续字符，也可以整个字符串都删除）$\Rightarrow$ 这样操作的代价为所有被删除的字符中字符 '1' 的个数与没有被删除的字符中字符 '0' 的个数的较大值。

举个例子，$s =$ '1001001001001'，此时选择前 $3$ 个字符和后 $4$ 个字符删除（即 '1001001001001'），则被删除的字符中字符 '1' 有 $3$ 个，没有被删除的字符中字符 '0' 有 $4$ 个，所以这样操作的代价为 $\max\{3, 4\} = 4$。

你希望选择一种操作，使得操作的代价最小。求：最小代价。

输入格式

一行，一个字符串 $s$。$s$ 仅由字符 '0' 和 '1' 组成且长度不超过 $2 \cdot 10^5$。

输出格式

输出一个整数，表示操作的最小代价。

101110110

1

1001001001001

3

0000111111

0

说明/提示

样例解释

• 样例1：一种最优方案是删除前 $2$ 个字符和后 $1$ 个字符（101110110），这样：删除的字符 '1' 共 $1$ 个，没有被删除的字符 '0' 共 $1$ 个，代价为 $\max\{ 1, 1 \} = 1$
• 样例2：一种最优方案是删除前 $6$ 个字符和后 $3$ 个字符（1001001001001），这样：删除的字符 '1' 共 $3$ 个，没有被删除的字符 '0' 共 $2$ 个，代价为 $\max\{ 3,2 \} = 3$
• 样例3：一种最优方案是删除前 $4$ 个字符，这样：删除的字符 '1' 共 $0$ 个，没有被删除的字符 '0' 共 $0$ 个，代价为 $\max\{ 0,0 \} = 0$

数据规模与约定

设 $|s|$ 表示字符串 $s$ 的长度，则：

• 对于 $20\%$ 的数据，$|s| \le 20$
• 对于 $40\%$ 的数据，$|s| \le 200$
• 对于 $60\%$ 的数据，$|s| \le 2000$
• 对于 $80\%$ 的数据，$|s| \le 20000$
• 对于 $100\%$ 的数据，$1 \le |s| \le 200000$ 且字符串 $s$ 仅由字符 '0' 和 '1' 构成