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?

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.

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 |