투표에서 이기기

엘레쿠아도르에서는 매우 특이한 투표 방식을 쓴다. 선거 시간이 되면 $n$명의 시민이 어떤 순서로든 투표소에 도착한다. 정당은 $1$번과 $2$번 두 곳뿐이다. 도착한 시민은 집계원이 아닌 이상 두 정당 중 한 곳에 투표한다. 집계원은 투표하지 않는다. 대신 자신이 도착한 시점에 두 정당의 득표 수를 센다. 한쪽의 득표 수가 다른 쪽보다 많으면 그 정당이 1점을 얻는다. 득표 수가 같으면 어느 정당도 점수를 얻지 못한다. 최종적으로 점수가 가장 많은 정당이 이긴다. 두 정당의 점수가 같으면 혼란이 일어난다.

당신은 $1$번 정당을 대표하는 엘레쿠아도르의 대통령이다. 다가오는 선거에서 자신의 집권이 끝날까 봐 걱정하고 있다. 다행히 방법이 있다. 당신은 국민 모두가 누구에게 투표할지, 누가 집계원인지, 그리고 모두의 도착 순서를 알고 있다. 적절한 전화를 걸면 집계원이 도착하는 시점에도 영향을 줄 수 있다. 한 번의 이동으로 도착 순서 목록에서 집계원을 바로 옆 사람과 맞바꿀 수 있다. 다만 인접한 두 비집계원끼리는 맞바꿀 수 없다.

$1$번 정당이 승리를 확실히 하려면 최소 몇 번 맞바꿔야 하는가?

첫째 줄에 정수 $n$($1 \le n \le 5\,000$)이 주어진다. 엘레쿠아도르의 시민 수다. 둘째 줄에는 길이가 $n$인 문자열 $s$가 주어진다. 문자열은 $0$, $1$, $2$로만 이루어지며, 시민이 투표소에 도착하는 순서를 나타낸다. $s_i$가 $1$ 또는 $2$이면 $i$번째 시민은 각각 $1$번 또는 $2$번 정당에 투표한다. $s_i$가 $0$이면 $i$번째 시민은 집계원이다.

$1$번 정당이 승리를 확실히 할 수 있으면 필요한 맞바꿈의 최소 횟수를 정수 하나로 출력한다. 그렇지 않으면 impossible을 출력한다.