Chef has an array A of length N consisting of 1 and -1 only.

In one operation, Chef can choose any index i (1≤ i ≤ N) and multiply the element A_{i} by -1.

Find the minimum number of operations required to make the sum of the array equal to 0. Output -1 if the sum of the array cannot be made 0.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case consists of a single integer N denoting the length of the array.
- Second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

------ Output Format ------ 

For each test case, output the minimum number of operations to make the sum of the array equal to 0. Output -1 if it is not possible to make the sum equal to 0.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 1000$
$A_{i} = 1$ or $A_{i} = -1$

----- Sample Input 1 ------ 
4
4
1 1 1 1
5
1 -1 1 -1 1
6
1 -1 -1 1 1 1
2
1 -1

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

----- explanation 1 ------ 
Test case $1$: The minimum number of operations required is $2$. In the first operation, change $A_{3}$ from $1$ to $-1$. Similarly, in the second operation, change $A_{4}$ from $1$ to $-1$. Thus, the sum of the final array is $1+1-1-1=0$.

Test case $2$: It can be proven that the sum of the array cannot be made equal to zero by making any number of operations.

Test case $3$: We can change $A_{1}$ from $1$ to $-1$ in one operation. Thus, the sum of the array becomes $-1-1-1+1+1+1=0$.

Test case $4$: The sum of the array is already zero. Thus we do not need to make any operations.

Source: codechef | Difficulty: EASY
Tags: Mathematics


Solutions:
for i in range(int(input())):
	a = int(input())
	m = list(map(int, input().split()))
	if len(m) % 2 == 0:
		print(abs(sum(m) // 2))
	else:
		print('-1')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if len(l) % 2 == 0:
		print(abs(sum(l) // 2))
	else:
		print(-1)


for _ in range(int(input())):
	b = int(input())
	a = list(map(int, input().split()))
	if len(a) % 2 == 0:
		print(abs(sum(a) // 2))
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ones = 0
	minus = 0
	for i in a:
		if i == 1:
			ones += 1
		if i == -1:
			minus += 1
	diff = abs(ones - minus)
	if diff % 2 != 0:
		print(-1)
	else:
		print(diff // 2)


for _ in range(int(input())):
	c = 0
	x = int(input())
	a = list(map(int, input().split()))
	for i in range(x):
		c = c + a[i]
	if c % 2 == 0:
		print(abs(c // 2))
	else:
		print('-1')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	s = 0
	for i in range(n):
		s += a[i]
	if s % 2 == 0:
		print(abs(s // 2))
	else:
		print('-1')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = a.count(1)
	y = a.count(-1)
	if len(a) % 2 != 0:
		print(-1)
	else:
		print(abs(x - y) // 2)


for i in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	j = 0
	count = 0
	while j < x:
		count = count + y[j]
		j += 1
	if x % 2 == 0:
		print(abs(count // 2))
	else:
		print(-1)


for i in range(int(input())):
	a = int(input())
	n = list(map(int, input().split()))
	b = n.count(-1)
	c = n.count(1)
	if len(n) % 2 != 0:
		print(-1)
	elif b > c:
		print(len(n) // 2 - c)
	elif c > b:
		print(len(n) // 2 - b)
	elif c == b:
		print(0)


T = int(input())
for t in range(0, T):
	N = int(input())
	lst = list(map(int, input().split()))
	b = lst.count(-1)
	c = lst.count(1)
	l = len(lst)
	if l % 2 != 0:
		print('-1')
	elif c == b:
		print('0')
	elif c > b:
		print(l // 2 - b)
	else:
		print(l // 2 - c)


for i in range(int(input())):
	n = int(input())
	su = 0
	l = list(map(int, input().split(' ')))
	for i in l:
		su += i
	if su < 0:
		su = -su
	if su % 2 == 0:
		z = True
	else:
		z = False
	if z:
		print(int(su / 2))
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if len(l) % 2 != 0:
		print('-1')
	else:
		a = l.count(1)
		b = l.count(-1)
		print(int(abs(a - b) / 2))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if len(a) % 2 == 0:
		l = a.count(1)
		b = n - l
		m = max(l, b)
		print(m - n // 2)
	else:
		print(-1)


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	c = 0
	for i in A:
		c += i
	c = abs(c)
	if c % 2 == 0:
		print(c // 2)
	else:
		print(-1)


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	c = 0
	for i in A:
		b = A.count(1)
		e = A.count(-1)
	if len(A) % 2 != 0:
		print(-1)
	else:
		if b > e:
			o = b - e
			print(o // 2)
		if b < e:
			i = e - b
			print(i // 2)
		if b == e:
			print(0)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	print(-1) if N % 2 else print(abs(sum(A) // 2))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = sum(arr)
	if n % 2 == 0:
		print(int(abs(s) / 2))
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	if n % 2 == 0:
		x = a.count('-1')
		y = a.count('1')
		print(abs(x - y) // 2)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	s = sum(lis)
	if n % 2 == 0:
		print(abs(s // 2))
	else:
		print('-1')


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	t = sum(p)
	if n % 2 == 0:
		print(abs(t // 2))
	else:
		print(-1)


for i in range(int(input())):
	b = int(input())
	c = tuple(map(int, input().split()))
	d = sum(c)
	if d % 2 != 0:
		print(-1)
	else:
		print(abs(d // 2))


import math
for i in range(int(input())):
	n = int(input())
	a = tuple(map(int, input().split()))
	z = sum(a)
	if z % 2 == 0:
		print(abs(z) // 2)
	else:
		print(-1)


a = int(input())
for i in range(a):
	b = int(input())
	c = [int(x) for x in input().split()]
	d = sum(c)
	if d % 2 != 0:
		print(-1)
	else:
		print(abs(d // 2))


for _ in range(int(input())):
	if int(input()) % 2 != 0:
		l = input()
		print(-1)
	else:
		l = list(map(int, input().split()))
		print(abs(l.count(1) - l.count(-1)) // 2)


for t in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	v = l.count(-1)
	v1 = l.count(1)
	if v == 0:
		if v1 % 2 == 0:
			print(v1 // 2)
		else:
			print(-1)
	elif v1 == 0:
		if v % 2 == 0:
			print(v // 2)
		else:
			print(-1)
	elif v == v1:
		print(0)
	else:
		v2 = abs(v - v1)
		if v2 % 2 == 0:
			print(v2 // 2)
		else:
			print(-1)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	a = sum(A)
	if N % 2 == 0:
		print(abs(a) // 2)
	else:
		print('-1')


for j in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = sum(l)
	if n % 2 == 0:
		print(abs(a) // 2)
	else:
		print('-1')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	o = 0
	if n % 2 != 0:
		print(-1)
	else:
		for i in range(n):
			if a[i] == 1:
				o = o + 1
		if o > int(n / 2):
			print(o - int(n / 2))
		else:
			print(int(n / 2) - o)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	w = a.count(1)
	x = a.count(-1)
	if n % 2 == 0:
		print(abs(w - x) // 2)
	else:
		print(-1)


t = int(input())
while t > 0:
	t = t - 1
	p = 0
	n = 0
	a = int(input())
	r = list(input().split())
	for i in range(a):
		if int(r[i]) < 0:
			n = n + 1
		else:
			p = p + 1
	if n >= p:
		m = n - p
		if m % 2 != 0:
			print('-1')
		else:
			print(m // 2)
	else:
		m = p - n
		if m % 2 != 0:
			print('-1')
		else:
			print(m // 2)


t = int(input())
for i in range(t):
	N = int(input())
	li = list(map(int, input().split()))
	c_1 = li.count(1)
	c_2 = li.count(-1)
	if N % 2 == 0:
		print(abs(c_1 - c_2) // 2)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = l.count(1)
	cn = l.count(-1)
	if n % 2 == 0:
		print(abs(c - cn) // 2)
	else:
		print('-1')


for _ in range(int(input())):
	k = int(input())
	l1 = list(map(int, input().split()))
	one = l1.count(1)
	none = l1.count(-1)
	if k % 2 == 0:
		oper = abs(one - none) // 2
		print(oper)
	else:
		print('-1')


t = int(input())
for i in range(t):
	d = 0
	c = 0
	n = int(input())
	a = list(map(int, input().split()))
	for j in range(n):
		if a[j] == -1:
			c = c - 1
		else:
			d = d + 1
	if (c + d) % 2 == 0 and c + d < 0:
		print(-(c + d) // 2)
	elif (c + d) % 2 == 0:
		print((c + d) // 2)
	else:
		print(-1)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	if N % 2 == 0:
		(c1, c2) = (0, 0)
		for i in A:
			if i == -1:
				c1 += 1
			else:
				c2 += 1
		print(abs(c2 - c1) // 2)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(c1, c2) = (0, 0)
	for i in l:
		if i == 1:
			c1 += 1
		else:
			c2 += 1
	if n % 2 == 0:
		print(abs(c1 - c2) // 2)
	else:
		print('-1')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = sum(a)
	c = len(a)
	if b < 0:
		b = b * -1
	if c % 2 != 0:
		print('-1')
	else:
		print(b // 2)


n = int(input())
for _ in range(n):
	t = int(input())
	l1 = list(map(int, input().split()))
	c1 = l1.count(-1)
	c2 = l1.count(1)
	if (c1 - c2) % 2 != 0:
		print(-1)
	else:
		print(abs(c1 - c2) // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(oc, moc) = (0, 0)
	if n % 2:
		print(-1)
	else:
		for i in range(n):
			if a[i] == 1:
				oc += 1
			else:
				moc += 1
		if oc == n or moc == n:
			print(n // 2)
		else:
			print(max(oc, moc) - n // 2)


T = int(input())
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	res = sum(a)
	if res % 2 == 0:
		print(abs(res // 2))
	else:
		print('-1')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = len(a)
	for i in range(s):
		c = a.count(1)
		d = a.count(-1)
	if c - d == 0:
		print(0)
	elif n % 2 != 0:
		print(-1)
	elif n % 2 == 0:
		print(abs(c - d) // 2)


n = int(input())
for i in range(n):
	x = int(input())
	l = list(map(int, input().split()))
	res = sum(l)
	if res % 2 == 0:
		print(abs(res // 2))
	else:
		print('-1')


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	result = sum(lst)
	print(abs(result // 2)) if result % 2 == 0 else print(-1)


def code():
	cases = int(input())
	for _ in range(cases):
		N = int(input())
		nums = list(map(int, input().split()))
		if N % 2 != 0:
			print(-1)
		else:
			pos_count = nums.count(1)
			if N // 2 == pos_count:
				print(0)
			elif pos_count < N // 2:
				print(N // 2 - pos_count)
			else:
				print(pos_count - N // 2)
code()


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n % 2 != 0:
		print(-1)
	else:
		c = 0
		for x in range(n):
			if l[x] == 1:
				c += 1
		if n // 2 == c:
			print(0)
		elif c < n // 2:
			print(n // 2 - c)
		else:
			print(c - n // 2)