Today is the day of the CCDSAP exam. Chef is responsible for monitoring the exam. The hall in which the exam will be held contains $N$ seats (numbered $1$ through $N$) arranged in a row. Initially, each seat is either empty or occupied by a participant in the exam. You are given a binary string $S$ with length $N$; for each valid $i$, the $i$-th character of $S$ is '1' if the $i$-th seat is occupied or '0' if this seat is empty.

Chef wants to make sure that no two participants are sitting next to each other, in order to prevent cheating. To do this, Chef may perform a number of operations (possibly zero). In each operation, he can ask a participant to move from his seat to an adjacent seat, either to its left or right, if such a seat exists and is empty.

Find the minimum number of operations required to make sure that no two participants are sitting next to each other (in adjacent seats), or determine that it is impossible.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains a single string $S$ with length $N$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum number of operations, or the string "impossible" if Chef cannot achieve his goal.

------  Constraints ------
$1 ≤ T ≤ 10,000$
$1 ≤ N ≤ 2 * 10^{5}$
the sum of $N$ over all test cases does not exceed $ 2 * 10^{5}$
the exam has at least one participant

------  Subtasks ------
Subtask #1 (50 points): the sum of $N$ over all test cases does not exceed $5,000$

Subtask #2 (50 points): original constraints

----- Sample Input 1 ------ 
4

3

011

5

10111

1

1

6

000111
----- Sample Output 1 ------ 
1

impossible

0

3

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Constructive algorithms

Ad-hoc


Solutions:
import sys
input = sys.stdin.readline
from sys import stdin, stdout
from math import ceil
import heapq

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input().strip()
		if n == 1:
			print(0)
			continue
		m = s.count('1')
		j = 1
		pos = [-1] * (m + 1)
		for i in range(n):
			if s[i] == '1':
				pos[j] = i + 1
				j += 1
			if j > m:
				break
		dp = [[[10 ** 9 + 7, 10 ** 9 + 7] for i in range(m + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				for filled in range(2):
					if j == 0:
						dp[i][j][filled] = 0
						continue
					if j > ceil(i / 2):
						continue
					if filled == 1:
						dp[i][j][filled] = dp[i - 1][j - 1][0] + abs(pos[j] - i)
					else:
						a = dp[i - 1][j][0]
						b = dp[i - 1][j][1]
						dp[i][j][filled] = min(a, b)
		ans = min(dp[n][m][0], dp[n][m][1])
		if ans == 10 ** 9 + 7:
			print('impossible')
		else:
			print(ans)

def main1():
	for _ in range(int(input())):
		n = int(input())
		s = input().strip()
		if n == 1:
			print(0)
			continue
		m = s.count('1')
		if m == 0:
			print(0)
			continue
		if m > (n + 1) // 2:
			print('impossible')
			continue
		j = 0
		pos = [-1] * m
		for i in range(n):
			if s[i] == '1':
				pos[j] = i
				j += 1
		heap = [0] * (m + 4)
		maxopt = n + 1 - 2 * m
		curropt = -10
		ans = 0
		for i in range(m):
			if -heap[0] <= pos[i] - 2 * i:
				curropt = min(maxopt, pos[i])
				heapq.heappush(heap, -(curropt - 2 * i))
			else:
				heapq.heappush(heap, -(pos[i] - 2 * i))
				curropt = -heap[0] + 2 * i
				heapq.heappop(heap)
				heapq.heappush(heap, -(pos[i] - 2 * i))
			ans += abs(curropt - pos[i])
			maxopt += 2
		print(ans)
main1()