P4989 Binary Mystery

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

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. #

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

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

For $30$% of the data, $0