Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a sequence $A_{1}, A_{2}, \ldots, A_{N}$. The sequence is circular, i.e. for each valid $i$, elements $A_{i}$ and $A_{i+1}$ are considered adjacent, and elements $A_{1}$ and $A_{N}$ are also considered adjacent. Initially, each element of this sequence is either $1$ or $0$.

You may perform some operations on this sequence. In one operation, you should choose an index $i$ such that $A_{i} = 1$ and move that $1$ to one of its adjacent elements, i.e. change $A_{i}$ to $0$, choose one of the elements adjacent to $A_{i}$ and increment it by $1$.

According to Chef, a sequence is *good* if all its elements are different from $1$. You have to tell Chef the minimum number of operations needed to turn the sequence $A$ into a good sequence 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 $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum number of required operations, or $-1$ if it is impossible to make the sequence good.

------  Constraints ------
$1 ≤ T ≤ 10^{4}$
$3 ≤ N ≤ 10^{6}$
$0 ≤ A_{i} ≤ 1$ for each valid $i$
the sum of $N$ over all test cases does not exceed $2 \cdot 10^{6}$

------  Subtasks ------
Subtask #1 (30 points):
$N = 1,000$
the sum of $N$ over all test cases does not exceed $10^{4}$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
3

3

0 0 0

4

1 0 1 0

5

1 1 0 1 0
----- Sample Output 1 ------ 
0

2

3
----- explanation 1 ------ 
Example case 1: The sequence is already good, so the answer is zero.

Example case 2: We can make the sequence good in two operations, e.g. $[1, 0, 1, 0] \rightarrow [0, 1, 1, 0] \rightarrow [0, 0, 2, 0]$.

Example case 3: We can make the sequence good in three operations, e.g. $[1, 1, 0, 1, 0] \rightarrow [0, 2, 0, 1, 0] \rightarrow [0, 2, 1, 0, 0] \rightarrow [0, 3, 0, 0, 0]$.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Ad-hoc


Solutions:
from sys import maxsize

def solve(ar):
	dp = [0] * (len(ar) + 1)
	dp[0] = 0
	dp[1] = maxsize
	dp[2] = ar[1] - ar[0]
	for i in range(3, len(ar) + 1):
		dp[i] = min(dp[i - 2] + ar[i - 1] - ar[i - 2], dp[i - 3] + ar[i - 1] - ar[i - 3])
	return dp[len(ar)]

def construct_arr(arr):
	ar = []
	for i in range(len(arr)):
		if arr[i]:
			ar.append(i)
	return ar
for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	ar = construct_arr(ls)
	if len(ar) == 0:
		print(0)
	elif len(ar) == 1:
		print(-1)
	else:
		ans1 = solve(ar)
		temp1 = ls[-(n - ar[-1]):] + ls[:-(n - ar[-1])]
		temp2 = ls[-(n - ar[-2]):] + ls[:-(n - ar[-2])]
		print(min((solve(ar), solve(construct_arr(temp1)), solve(construct_arr(temp2)))))


def solve(v):
	dp[0] = 0
	dp[1] = 10 ** 9
	dp[2] = v[1] - v[0]
	for i in range(3, len(v) + 1):
		dp[i] = min(v[i - 1] - v[i - 2] + dp[i - 2], v[i - 1] - v[i - 3] + dp[i - 3])
	return dp[len(v)]
dp = [0 for i in range(10 ** 6 + 10)]
for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	v = []
	for i in range(n):
		if ls[i] == 1:
			v.append(i)
	if len(v) == 0:
		print(0)
		continue
	if len(v) == 1:
		print(-1)
		continue
	ans = 10 ** 9
	ans = min(ans, solve(v))
	temp = v[0]
	for i in range(len(v) - 1):
		v[i] = v[i + 1] - (temp + 1)
	v[-1] = n - 1
	ans = min(ans, solve(v))
	temp = v[0]
	for i in range(len(v) - 1):
		v[i] = v[i + 1] - (temp + 1)
	v[-1] = n - 1
	ans = min(ans, solve(v))
	print(ans)


def main():

	def solve():
		n = int(input())
		aa = [int(a) for a in input().split()]
		onepos = []
		for (i, a) in enumerate(aa):
			if a == 1:
				onepos.append(i)
		lo = len(onepos)
		if lo == 0:
			print(0)
			return
		if lo == 1:
			print(-1)
			return
		costs = (0, n)
		for i in range(1, lo):
			costs = (costs[1], min(costs[0], costs[1]) + onepos[i] - onepos[i - 1])
		c0 = costs[1]
		costs = (0, n)
		for i in range(2, lo + 1):
			costs = (costs[1], min(costs[0], costs[1]) + (onepos[i % lo] - onepos[(i - 1) % lo]) % n)
		c1 = costs[1]
		costs = (0, n)
		for i in range(3, lo + 2):
			costs = (costs[1], min(costs[0], costs[1]) + (onepos[i % lo] - onepos[(i - 1) % lo]) % n)
		c2 = costs[1]
		print(min(c0, c1, c2))
	q = int(input())
	for _ in range(q):
		solve()
main()


def solve(ar):
	dp = [0] + [9223372036854775807] + [0] * (len(ar) - 1)
	dp[2] = ar[1] - ar[0]
	for i in range(3, len(ar) + 1):
		dp[i] = min(dp[i - 2] + ar[i - 1] - ar[i - 2], dp[i - 3] + ar[i - 1] - ar[i - 3])
	return dp[len(ar)]

def cr(arr, ar):
	for i in range(len(arr)):
		if arr[i]:
			ar.append(i)
	return ar
for _ in range(int(input())):
	(n, ls) = (int(input()), list(map(int, input().split())))
	ar = cr(ls, [])
	print(-len(ar)) if len(ar) == 0 or len(ar) == 1 else print(min((solve(ar), solve(cr(ls[-(n - ar[-1]):] + ls[:-(n - ar[-1])], [])), solve(cr(ls[-(n - ar[-2]):] + ls[:-(n - ar[-2])], [])))))


from sys import maxsize
from copy import deepcopy
from math import gcd

def leftRotate(arr, d):
	n = len(arr)
	d = d % n
	g_c_d = gcd(d, n)
	for i in range(g_c_d):
		temp = arr[i]
		j = i
		while 1:
			k = j + d
			if k >= n:
				k = k - n
			if k == i:
				break
			arr[j] = arr[k]
			j = k
		arr[j] = temp

def solve(ar):
	dp = [0] * (len(ar) + 1)
	dp[0] = 0
	dp[1] = maxsize
	dp[2] = ar[1] - ar[0]
	for i in range(3, len(ar) + 1):
		dp[i] = min(dp[i - 2] + ar[i - 1] - ar[i - 2], dp[i - 3] + ar[i - 1] - ar[i - 3])
	return dp[len(ar)]

def construct_arr(arr):
	ar = []
	for i in range(len(arr)):
		if arr[i]:
			ar.append(i)
	return ar
for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	ar = construct_arr(ls)
	if len(ar) == 0:
		print(0)
	elif len(ar) == 1:
		print(-1)
	else:
		ans1 = solve(ar)
		temp1 = ls[-(n - ar[-1]):] + ls[:-(n - ar[-1])]
		temp2 = ls[-(n - ar[-2]):] + ls[:-(n - ar[-2])]
		print(min((solve(ar), solve(construct_arr(temp1)), solve(construct_arr(temp2)))))