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.

Background

Special for beginners, ^_^

Description

给出一个长度为n的01字符串(至少包含一个1)，我们可以做的操作是将相邻两个字符互换位置。 请求出将所有1连在一起所需要的最少操作数。

Format

2≤N≤5×10 e5

Input

Output

最少操作数

Samples

7
0101001

3

解释：

例如，以下三个操作使所有1连续：

选择i=2并交换第二个和第三个字符。那么，S=0011001。

选择i=6并交换第6和第7个字符。那么，S=0011010。

选择i=5并交换第5和第6个字符。那么，S=0011100。

不可能在两个或更少的操作中做到这一点，因此答案是3。

Limitation

1s, 1024KiB for each test case.