Background

Although she has already passed $Faded$, Xiaomai still did not solve the binary mystery.

Problem Description

At this moment, she sensed that there might be some special possible correspondence between $0$ and $1$. So, she defined the “inspiration coefficient” as the absolute value of the difference between the digit positions (counted from high to low) of a corresponding pair. She now wants to match $0$ with $1$ so that, while maximizing the number of correspondences, the sum of inspiration coefficients is as large as possible.

The matching rules are as follows:

$1$. Each correspondence must start with $0$ and end with $1$; in other words, in every correspondence, $0$ must be before (higher bit), and $1$ must be after (lower bit).

$2$. You may choose several correspondences, but correspondences must not cross. The meaning of crossing is: they share some interval and it is not a containment relationship.

$e.g.$ Suppose one correspondence is between the $2$-nd digit and the $4$-th digit, and another correspondence is between the $3$-rd digit and the $5$-th digit. Then they cannot both be chosen, because they cross on the interval $[3,4]$. However, if the correspondences are between the $1$-st and $5$-th digits, and between the $2$-nd and $4$-th digits, then this is not considered crossing, because although they share the interval $[2,4]$, there is a containment relationship, so they can both be chosen.

That is, crossing is not the same as intersection.

$3$. Each digit can appear in at most one correspondence.

Input Format

The first line contains an integer $n$, the number of bits in the binary number.

The next line contains an $n$-bit binary number.

Output Format

One line, representing the maximum possible sum of inspiration coefficients under the condition that the number of correspondences is maximized.

2
10

0

6
110100

1

Hint

For $30$% of the data, $0<n<=20$.

For $100$% of the data, $0<n<=300$.

Sample Explanation

For sample 1, since $1$ is before $0$, they cannot be matched.

For sample 2, the matching plan is $3-4$, so the total sum is $1$.

If you have already $AK$, you can try the Enhanced Data Version.

Translated by ChatGPT 5