Pattern: 2 DSA + 1 SQL

You are given a binary string s of length n, containing only '0' and '1'.

You may perform a swap between any two positions in the string. Your goal is to make all the 1s form one contiguous segment.

Find the minimum number of swaps required to obtain the maximum possible length of consecutive 1s.

Input

• The first line contains an integer n — the length of the binary string.
• The second line contains the binary string s.

Output

Print a single integer — the minimum number of swaps required to make all 1s consecutive.

Constraints

• 1 ≤ n ≤ 2 × 10^5
• s consists only of '0' and '1'.
• The string contains at least one 1.

Examples

Example 1

Input:
8
10010011

Output:
1

Explanation: There are four 1s. We can make them consecutive as 01111000 using one swap.

Example 2

Input:
7
1010101

Output:
2

Explanation: There are four 1s. Choosing a window of length 4, such as 1010, requires two swaps to make it 1111.

Example 3

Input:
5
11101

Output:
0

Explanation: The first three 1s are already consecutive, so no swaps are required.