You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给定一个只由 $0$ 与 $1$ 构成序列，不断扫描序列，如果发现有一个 $1$ 与一个 $0$ 相邻，且 $1$ 在前，$0$ 在后，就交换它们的位置。不断进行调整直到将所有的 $0$ 都在序列的前一半，所有的 $1$ 都在序列的后一半为止。

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

Format

Input

若干 01 字符组成的一个序列

Output

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

Samples

010101

3

Limitation

1s, 1024KiB for each test case.

设 $n$ 表示序列的长度，

$30\%$ 的数据，$1≤n≤20$

$60\%$ 的数据，$1≤n≤5000$

$100\%$ 的数据，$1≤n≤300,000$