310616: CF1860D. Balanced String

D. Balanced Stringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a binary string $s$ (a binary string is a string consisting of characters 0 and/or 1).

Let's call a binary string balanced if the number of subsequences 01 (the number of indices $i$ and $j$ such that $1 \le i < j \le n$, $s_i=0$ and $s_j=1$) equals to the number of subsequences 10 (the number of indices $k$ and $l$ such that $1 \le k < l \le n$, $s_k=1$ and $s_l=0$) in it.

For example, the string 1000110 is balanced, because both the number of subsequences 01 and the number of subsequences 10 are equal to $6$. On the other hand, 11010 is not balanced, because the number of subsequences 01 is $1$, but the number of subsequences 10 is $5$.

You can perform the following operation any number of times: choose two characters in $s$ and swap them. Your task is to calculate the minimum number of operations to make the string $s$ balanced.

Input

The only line contains the string $s$ ($3 \le |s| \le 100$) consisting of characters 0 and/or 1.

Additional constraint on the input: the string $s$ can be made balanced.

Output

Print a single integer — the minimum number of swap operations to make the string $s$ balanced.

ExamplesInput

101

Output

0

Input

1000110

Output

0

Input

11010

Output

1

Input

11001100

Output

2

Note

In the first example, the string is already balanced, the number of both 01 and 10 is equal to $1$.

In the second example, the string is already balanced, the number of both 01 and 10 is equal to $6$.

In the third example, one of the possible answers is the following one: 11010 $\rightarrow$ 01110. After that, the number of both 01 and 10 is equal to $3$.

In the fourth example, one of the possible answers is the following one: 11001100 $\rightarrow$ 11001010 $\rightarrow$ 11000011. After that, the number of both 01 and 10 is equal to $8$.

题目大意：给定一个由字符 '0' 和 '1' 组成的二进制字符串 s。如果 s 中子序列 "01"（即满足 1 ≤ i < j ≤ n，s_i=0 和 s_j=1 的索引对 (i, j) 的数量）的数量等于子序列 "10"（即满足 1 ≤ k < l ≤ n，s_k=1 和 s_l=0 的索引对 (k, l) 的数量）的数量，则称该字符串是平衡的。可以通过任意次数的选择字符串 s 中的两个字符并交换它们来操作字符串。求使字符串 s 平衡所需的最小交换次数。

输入数据格式：输入只有一行，包含一个字符串 s（3 ≤ |s| ≤ 100），s 由字符 '0' 和 '1' 组成。输入的字符串 s 可以被调整为平衡状态。

输出数据格式：输出一个整数，表示使字符串 s 平衡所需的最小交换操作次数。

示例：

输入：101
输出：0

输入：1000110
输出：0

输入：11010
输出：1

输入：11001100
输出：2

注意：在第一个示例中，字符串已经平衡，"01" 和 "10" 的数量都是 1。在第二个示例中，字符串已经平衡，"01" 和 "10" 的数量都是 6。在第三个示例中，一个可能的答案是：11010 → 01110。之后，"01" 和 "10" 的数量都是 3。在第四个示例中，一个可能的答案是：11001100 → 11001010 → 11000011。之后，"01" 和 "10" 的数量都是 8。题目大意：给定一个由字符 '0' 和 '1' 组成的二进制字符串 s。如果 s 中子序列 "01"（即满足 1 ≤ i < j ≤ n，s_i=0 和 s_j=1 的索引对 (i, j) 的数量）的数量等于子序列 "10"（即满足 1 ≤ k < l ≤ n，s_k=1 和 s_l=0 的索引对 (k, l) 的数量）的数量，则称该字符串是平衡的。可以通过任意次数的选择字符串 s 中的两个字符并交换它们来操作字符串。求使字符串 s 平衡所需的最小交换次数。 输入数据格式：输入只有一行，包含一个字符串 s（3 ≤ |s| ≤ 100），s 由字符 '0' 和 '1' 组成。输入的字符串 s 可以被调整为平衡状态。 输出数据格式：输出一个整数，表示使字符串 s 平衡所需的最小交换操作次数。 示例： 输入：101 输出：0 输入：1000110 输出：0 输入：11010 输出：1 输入：11001100 输出：2 注意：在第一个示例中，字符串已经平衡，"01" 和 "10" 的数量都是 1。在第二个示例中，字符串已经平衡，"01" 和 "10" 的数量都是 6。在第三个示例中，一个可能的答案是：11010 → 01110。之后，"01" 和 "10" 的数量都是 3。在第四个示例中，一个可能的答案是：11001100 → 11001010 → 11000011。之后，"01" 和 "10" 的数量都是 8。