Hide

Problem FPaired Furnaces

Just outside the entrance to your mine shaft you have a row of $n$ furnaces; some of them are on and some are off. Unlike regular furnaces, these furnaces can only be turned on in neighboring pairs. In one move you can either choose two neighboring furnaces which are on and turn both of them off, or choose two neighboring furnaces which are off and turn both of them on.

You want to turn all of them on as quickly as possible. If it is possible to turn all the furnaces on, output the minimum number of moves to do so. Otherwise, output “impossible”.

Input

The first line contains one integer $n$, $1 \leq n \leq 10^6$. The next line contains a binary string $s$ of length $n$, where $s_ i=0$ means the $i$th furnace in the row is off and $s_ i=1$ means the $i$th furnace in the row is on.

Output

The minimum number of moves to turn all of the furnaces on, or “impossible” if it is not possible to do so.

Sample Input 1 Sample Output 1
1
0

impossible

Sample Input 2 Sample Output 2
4
0110

3

Sample Input 3 Sample Output 3
12
010101101010

21


Please log in to submit a solution to this problem