Problem H
Winning the Vote
In the country of Elecuador, a very strange voting system is used. When it is time for the election, each one of the $n$ citizens will arrive in some order to the voting station. There are only two parties to vote for, conveniently named $1$ and $2$. When arriving to the voting station, a person will vote for one of the parties, unless they are a teller. The tellers do not vote, instead they count how many votes each of the two parties has at the time the teller arrives, and if one of the parties has more votes than the other then that party receives one point (if the two parties have the same number of votes, neither of them receives a point). The party with the most points at the end wins. If both parties end up with the same number of points, chaos ensues.
As the president of Elecuador representing party $1$, you are worried that the coming election will be the end of your reign. Fortunately, you have a plan to stop this from happening. Being the president, you know who everyone in the country will vote for, who the tellers are, and in what order everyone will arrive to the voting station. By making the right phone calls, you can also affect when the tellers arrive. In one move, it is possible to swap a teller with an adjacent person in the list of arrivals to the voting station. Note that it is not possible to swap two adjacent non-tellers. What is the minimum number of swaps necessary to ensure that party $1$ wins?
Input
The input starts with a line containing an integer $n$ $n$ ($1 \le n \le 5\, 000$), the number of citizens in Elecuador. Then follows a line containing a string $s$ of length $n$, consisting of the characters $0$, $1$, and $2$. This string represents the citizens in the order they arrive to the voting station. If the $i$’th character $s_ i$ is $1$ or $2$, it means that the $i$’th citizen will vote for party $1$ or $2$, respectively. If $s_ i$ is $0$, it means that the $i$’th citizen is a teller.
Output
If it is possible to ensure victory, output one integer, the minimum number of swaps necessary. Otherwise, output “impossible”.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 12210020 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 1111 |
impossible |
| Sample Input 3 | Sample Output 3 |
|---|---|
11 00211222220 |
5 |
