Minimum Swaps to Achieve a Good 0-1 Sequence

A binary (0-1) sequence \(\{a_i\}_{i=1}^n\) is said to be good if when we cover all the \(1\)s by its maximal contiguous segments, the lengths of these segments are strictly increasing from left to right. In other words, if the unique covering (i.e. every \(1\) lies in exactly one interval) is given by intervals \(\{[l_j,r_j]\}_{j=1}^k\) (so that \(a_i=1\) if and only if \(i\in[l_j,r_j]\) for some \(j\)) then the sequence is good if and only if \[ \forall j\in[1,k-1],\quad r_j-l_j<r_{j+1}-l_{j+1}, \] which means that the lengths of the consecutive segments of ones, when read from left to right, are strictly increasing.

You are allowed to perform the following operation any number of times (possibly zero): choose two distinct indices \(i,j\) (with \(i\neq j\)) and swap \(a_i\) and \(a_j\). Determine the minimum number of swaps required to transform the given sequence into a good sequence.

Note. The number of swaps required to transform one binary sequence into another is defined as \(m - X\), where \(m\) is the total number of \(1\)s in the sequence and \(X\) is the maximum number of positions that are already \(1\) in both the original and the target sequence. Since any good sequence will have exactly \(m\) ones arranged into some contiguous blocks with strictly increasing lengths (when these blocks are taken in order), the goal reduces to choosing a set of \(m\) positions which is "good" (i.e. its runs of consecutive integers have strictly increasing lengths) and which has maximum overlap with the positions of the \(1\)s in the original sequence. It can be shown that for any binary sequence, there exists at least one good pattern (for instance, having a single block of \(m\) consecutive ones is always good).

Input Format: The first line contains a single integer \(n\) (the length of the sequence). The second line contains a binary string of length \(n\) consisting only of characters '0' and '1'.

Output Format: Output a single integer, the minimum number of swaps required to make the sequence good.

inputFormat

The first line contains an integer \(n\) \((1 \leq n \leq 50)\), the length of the sequence. The second line contains a binary string of length \(n\) consisting of characters '0' and '1'.

outputFormat

Output a single integer representing the minimum number of swaps needed to transform the sequence into a good sequence.

sample

5
01101

1