给定一个二进制字符串 $$$s$$$(二进制字符串是由字符 0 和/或 1 组成的字符串)。
如果子序列 01 的数量(索引 $$$i$$$ 和 $$$j$$$ 的数量,使得 $$$1 \le i < j \le n$$$、$$$s_i=0$$$ 和 $$$s_j=1$$$)等于子序列 10 的数量(索引 $$$k$$$ 的数量),我们称二进制字符串是平衡的和 $$$l$$$ 使得 $$$1 \le k < l \le n$$$, $$$s_k=1$$$ 和 $$$s_l=0$$$) 。
例如,字符串 1000110 是平衡的,因为子序列 01 的数量和子序列 10 的数量都等于 $$$6$$$。另一方面,11010是不平衡的,因为子序列01的数量是$$$1$$$,但是子序列10的数量是$$$5$$$。
您可以多次执行以下操作:在 $$$s$$$ 中选择两个字符并交换它们。你的任务是计算使字符串 $$$s$$$ 平衡所需的最少操作数。
输入
唯一一行包含由字符 0 和/或 1 组成的字符串 $$$s$$$ ($$$3 \le |s| \le 100$$$)。
输入的附加约束:字符串 $$$s$$$ 可以平衡。
输出
打印单个整数 - 使字符串 $$$s$$$ 平衡的交换操作的最小数量。
示例
输入 #1
101
输出 #1
0
输入 #2
1000110
输出 #2
0
输入 #3
11010
输出 #3
1
输入#4
11001100
输出#4
2
注意
在第一个示例中,字符串已经平衡,01 和 10 的数量都等于 $$$1$$$。
在第二个示例中,字符串已经平衡,01 和 10 的数量都等于 $$$6$$$。
在第三个示例中,可能的答案之一如下:11010 $$$\rightarrow$$$ 01110。之后,01 和 10 的数字都等于 $$$3$$$。
在第四个示例中,可能的答案之一如下: 11001100 $$$\rightarrow$$$ 11001010 $$$\rightarrow$$$ 11000011。之后,01 和 10 的数字都等于 $$$8$$$。