交换的轮数

题目描述

给定一个只由 $0$ 与 $1$ 构成序列，不断扫描序列，在每一轮扫描的过程中，如果发现有一些 $1$ 与 $0$ 相邻，且 $1$ 在前，$0$ 在后，就在这一轮扫描后，同时将这些 $1$ 与相邻的 $0$ 交换。不断进行调整直到将所有的 $0$ 都在序列的前一半，所有的 $1$ 都在序列的后一半为止。

请计算需要进行多少轮交换才能完成调整。

输入格式

• 一个由若干 0 和 1 字符组成的序列。

输出格式

• 单个整数：表示交换的次数。

数据范围

• 对于 $30\%$ 的数据，$1 \leq n \leq 20$
• 对于 $60\%$ 的数据，$1 \leq n \leq 5000$
• 对于 $100\%$ 的数据，$1 \leq n \leq 300,000$

样例数据

输入:

1100

输出:

3

在这个例子中，每一轮扫描将进行如下操作：

1. 第一轮将 1100 变为 1001 (进行一次交换)
2. 第二轮将 1001 变为 0101 (进行一次交换)
3. 第三轮将 0101 变为 0011 (进行一次交换)

总共需要三轮交换来完成所有的 $0$ 在前和所有的 $1$ 在后的目标。