Andrew has $n$ piles with stones. The $i$-th pile contains $a_i$ stones. He wants to make his table clean so he decided to put every stone either to the $1$-st or the $n$-th pile.

Andrew can perform the following operation any number of times: choose $3$ indices $1 \le i < j < k \le n$, such that the $j$-th pile contains at least $2$ stones, then he takes $2$ stones from the pile $j$ and puts one stone into pile $i$ and one stone into pile $k$.

Tell Andrew what is the minimum number of operations needed to move all the stones to piles $1$ and $n$, or determine if it's impossible.


-----Input-----

The input contains several test cases. The first line contains one integer $t$ ($1 \leq t \leq 10000$) — the number of test cases.

The first line for each test case contains one integer $n$ ($3 \leq n \leq 10^5$) — the length of the array.

The second line contains a sequence of integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the array elements.

It is guaranteed that the sum of the values $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print the minimum number of operations needed to move stones to piles $1$ and $n$, or print $-1$ if it's impossible.


-----Examples-----

Input
4
5
1 2 2 3 6
3
1 3 1
3
1 2 1
4
3 1 1 2
Output
4
-1
1
-1


-----Note-----

In the first test case, it is optimal to do the following:

Select $(i, j, k) = (1, 2, 5)$. The array becomes equal to $[2, 0, 2, 3, 7]$.

Select $(i, j, k) = (1, 3, 4)$. The array becomes equal to $[3, 0, 0, 4, 7]$.

Twice select $(i, j, k) = (1, 4, 5)$. The array becomes equal to $[5, 0, 0, 0, 9]$. This array satisfy the statement, because every stone is moved to piles $1$ and $5$.

There are $4$ operations in total.

In the second test case, it's impossible to put all stones into piles with numbers $1$ and $3$:

At the beginning there's only one possible operation with $(i, j, k) = (1, 2, 3)$. The array becomes equal to $[2, 1, 2]$.

Now there is no possible operation and the array doesn't satisfy the statement, so the answer is $-1$.

In the third test case, it's optimal to do the following:

Select $(i, j, k) = (1, 2, 3)$. The array becomes equal to $[2, 0, 2]$. This array satisfies the statement, because every stone is moved to piles $1$ and $3$.

The is $1$ operation in total.

In the fourth test case, it's impossible to do any operation, and the array doesn't satisfy the statement, so the answer is $-1$.

Source: codeforces | Difficulty: EASY
Tags: Implementation

Greedy algorithms


Solutions:
for s in [*open(0)][2::2]:
	a = list(map(int, s.split()))[1:-1]
	if len(a) == 1 and a[0] & 1 or a.count(1) == len(a):
		print(-1)
	else:
		print(sum([(i + 1) // 2 for i in a]))


import sys
import bisect
inp = sys.stdin.readline

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(inp())):
	n = int(inp())
	a = [int(i) for i in inp().split()]
	for i in a[1:n - 1]:
		if i != 1:
			if n == 3 and a[1] % 2:
				print(-1)
			else:
				ans = 0
				for i in a[1:n - 1]:
					ans += (i + 1) // 2
				print(ans)
			break
	else:
		print(-1)


def main():
	import sys
	inp = sys.stdin.readline
	test = int(input())
	while test:
		n = int(inp())
		s = [*map(int, inp().split())]
		col_nech = 0
		col_pairs = 0
		for i in range(1, n - 1):
			col_pairs += s[i] // 2
			if s[i] % 2:
				col_nech += 1
		if len(s) == 3:
			if s[1] % 2:
				print(-1)
			else:
				print(col_pairs)
		elif not col_pairs:
			print(-1)
		else:
			print(col_nech + col_pairs)
		test -= 1
main()


import sys
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10 ** 9)

def inp():
	return int(input())

def read_int_list():
	return list(map(int, input().split()))

def read_list():
	s = input()
	return list(s[:len(s) - 1])

def read_int_map():
	return map(int, input().split())

def solve(a):
	if len(a) == 3:
		if a[1] % 2 == 1:
			return -1
	mid = a[1:-1]
	if all([value == 1 for value in mid]):
		return -1
	return sum([(value + 1) // 2 for value in mid])
for _ in range(inp()):
	_ = inp()
	print(solve(read_int_list()))


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	ok = False
	have = False
	r = 0
	for i in range(1, n - 1):
		ok = ok or a[i] > 1
		have = have or a[i] > 0
		r += a[i] // 2
		r += a[i] % 2
	if n == 3 and a[i] % 2 == 1:
		print(-1)
	elif have and (not ok):
		print(-1)
	else:
		print(r)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	moves = 0
	solos = 0
	for i in range(1, n - 1):
		moves += a[i] // 2
		solos += a[i] % 2
	if n == 3:
		if a[1] % 2 == 1:
			print(-1)
		else:
			print(moves)
	elif moves:
		moves += solos
		print(moves)
	else:
		print(-1)


import math as m
i = input()
inp = []
for a in range(0, int(i)):
	input()
	inp += [input()]
for s in inp:
	arr = [int(x) for x in s.split()]
	cannot = len(arr) == 3 and arr[1] % 2 == 1
	no_moves = True
	s = 0
	for x in arr[1:-1]:
		if x > 1:
			no_moves = False
		if x % 2 == 0:
			s += x
		else:
			s += x + 1
	cannot = cannot or no_moves
	if cannot:
		print(-1)
	else:
		print(s // 2)


import sys

def rall():
	return sys.stdin.readlines()

def rl():
	return sys.stdin.readline().strip()

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
NT = int(rl())
for ti in range(NT):
	_ = rl()
	array = list(map(int, rl().split(' ')))
	if len(array) < 3:
		pr(0)
	else:
		insides = array[1:-1]
		can_give = len([a for a in insides if a >= 2])
		if can_give == 0:
			pr(-1)
		elif len(array) == 3 and array[1] % 2 == 1:
			pr(-1)
		else:
			total = 0
			for a in insides:
				if a % 2 == 0:
					total += a // 2
				else:
					total += (a + 1) // 2
			pr(total)


import sys
inp = [a.strip() for a in sys.stdin.readlines()]
t = int(inp[0])
k = 1
for _ in range(t):
	n = int(inp[k])
	k += 1
	l = [int(x) for x in inp[k].split()]
	k += 1
	k_pair = 0
	k_n_pair = 0
	for i in l[1:-1]:
		if i % 2 == 0:
			k_pair += 1
		else:
			k_n_pair += 1
	s = sum(l[1:-1])
	f = False
	for i in l[1:-1]:
		if i > 1:
			f = True
	if len(l) == 3 and l[1] % 2 != 0:
		print('-1')
		continue
	if not f:
		print('-1')
		continue
	print(s // 2 + (k_n_pair // 2 + k_n_pair % 2))


import sys
input = sys.stdin.readline

def solve(n, arr):
	if n == 3 and arr[1] % 2 or list(set(arr[1:n - 1])) == [1]:
		return -1
	ans = 0
	for i in range(1, n - 1):
		ans += arr[i] // 2 + arr[i] % 2
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


import math
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	l = 0
	res = 0
	if n == 3:
		if a[1] % 2:
			print(-1)
		else:
			print(a[1] // 2)
		continue
	ans = 1
	for i in range(1, n - 1):
		if a[i] > 1:
			ans = 0
	if ans:
		print(-1)
		continue
	for i in range(1, n - 1):
		l += (a[i] + 1) // 2
	print(l)


import math
for s in [*open(0)][2::2]:
	a = [*map(int, s.split())]
	if len(a) == 3 and a[1] % 2:
		print(-1)
		continue
	for i in range(1, len(a) - 1):
		if a[i] != 1:
			break
	else:
		print(-1)
		continue
	total_cost = 0
	for i in range(1, len(a) - 1):
		if a[i] % 2:
			total_cost += (a[i] + 1) // 2
		else:
			total_cost += a[i] // 2
	print(total_cost)


import sys

def solve():
	l = int(sys.stdin.readline().rstrip('\n'))
	arr = sys.stdin.readline().rstrip('\n').split(' ')
	arr = [int(_) for _ in arr]
	res = 0
	ev = 0
	od = 0
	ess = 0
	for i in range(1, l - 1):
		if arr[i] % 2 == 0:
			res += arr[i] // 2
			ev += 1
		else:
			od += 1
			res += arr[i] // 2 + 1
		if arr[i] == 1:
			ess += 1
	if od == 1 and ev == 0 or ess == l - 2:
		print(-1)
	else:
		print(res)
T = sys.stdin.readline().rstrip('\n')
for i in range(int(T)):
	solve()


import sys
n = int(sys.stdin.readline())
for test in range(n):
	(d, jishuge) = (0, 0)
	t = int(sys.stdin.readline())
	data = list(map(int, sys.stdin.readline().split()))
	for i in range(1, t - 1):
		jishuge += data[i] % 2
		d += data[i] // 2
	if jishuge and t == 3 or d == 0:
		print(-1)
		continue
	print(d + jishuge)


import sys
input = lambda : sys.stdin.readline().strip()
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	hap = 0
	cnt1 = 0
	odd = 0
	for i in range(1, n - 1):
		if arr[i] % 2 == 1:
			if arr[i] == 1:
				cnt1 += 1
			odd += 1
		hap += arr[i] // 2
	if n - 2 == cnt1:
		print(-1)
	elif n == 3 and arr[1] % 2 == 1:
		print(-1)
	else:
		print(hap + odd)


import sys
from math import ceil
input = sys.stdin.readline

def multiple():
	a = map(int, input().split())
	return a

def array():
	a = input().split()
	return a

def intarray():
	a = list(map(int, input().split()))
	return a

def getmex(arr):
	zeros = 0
	for i in arr:
		if i == 0:
			zeros += 1
	ans = len(arr) + zeros
	return ans

def solution():
	n = int(input())
	a = intarray()
	ans = 0
	wholeturns = 0
	odds = 0
	for i in range(1, n - 1):
		ans += ceil(a[i] / 2)
		wholeturns += a[i] // 2
		if a[i] % 2 == 1:
			odds += 1
	if wholeturns == 0:
		ans = -1
	if len(a) == 3 and a[1] % 2 == 1:
		ans = -1
	print(ans)
	return
t = int(input())
for _ in range(t):
	solution()


import sys

def func_3(my_list):
	if len(my_list) == 3 and my_list[1] % 2 != 0:
		return -1
	if my_list[1:len(my_list) - 1] == [1] * (len(my_list) - 2):
		return -1
	count = 0
	for i in my_list[1:len(my_list) - 1]:
		if i % 2 == 0:
			count += i // 2
		else:
			count += (i + 1) // 2
	return count

def main():
	reader = (list(map(int, line.split())) for line in sys.stdin)
	n = next(reader)[0]
	for _ in range(n):
		_ = next(reader)
		print(func_3(next(reader)))

def tests():
	assert func_3([1, 2, 2, 3, 6]) == 4
	assert func_3([1, 3, 1]) == -1
	assert func_3([1, 2, 1]) == 1
	assert func_3([3, 1, 1, 2]) == -1
	assert func_3([1, 1, 1]) == -1
	assert func_3([1, 2, 1]) == 1
	assert func_3([1, 1, 2, 1]) == 2
	assert func_3([1, 1, 1, 4, 1]) == 4
	assert func_3([1, 1, 4, 1, 1]) == 4
	assert func_3([1, 1, 2, 1, 1]) == 3
	assert func_3([1, 1, 1, 1, 2, 1, 1, 1, 1]) == 7
	assert func_3([1, 1, 1, 1, 1, 2, 1]) == 5
	assert func_3([1, 1, 1, 4, 1, 1, 1]) == 6
	assert func_3([1, 3, 5, 7, 1]) == 9
main()


t = int(input())
ans = []
for i in range(t):
	k = 0
	cmp = 0
	n = int(input())
	L = [int(x) for x in input().split()]
	if n > 3:
		for j in range(1, n - 1):
			if L[j] % 2 == 1:
				k += L[j] // 2 + 1
				if L[j] == 1:
					cmp += 1
			else:
				k += L[j] // 2
		if cmp == n - 2:
			ans.append(-1)
		else:
			ans.append(k)
	elif L[1] % 2 == 1:
		ans.append(-1)
	else:
		ans.append(L[1] // 2)
for i in range(t):
	print(ans[i])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	middle_a = a[1:n - 1]
	judge = False
	for num in middle_a:
		if num >= 2:
			judge = True
			break
	if not judge:
		print(-1)
	elif n == 3 and middle_a[0] % 2 == 1:
		print(-1)
	else:
		total = 0
		for num in middle_a:
			if num % 2 == 0:
				total += num // 2
			else:
				total += (num + 1) // 2
		print(total)


for _ in range(0, int(input())):
	input()
	v = list(map(int, input().split()))[1:-1]
	if len(v) == 1 and v[0] % 2 == 1 or v.count(1) == len(v):
		print(-1)
	else:
		print(sum((0 - -i // 2 for i in v)))


def func():
	n = int(input())
	l = list(map(int, input().split()))
	if n == 3 and l[1] % 2:
		return -1
	if max(l[1:n - 1]) == 1:
		return -1
	req = 0
	for i in l[1:n - 1]:
		req += (i + 1) // 2
	return req
t = int(input())
for i in range(t):
	print(func())


for _ in range(int(input())):
	size = int(input())
	arr = list(map(int, input().split()))
	arr = arr[1:-1]
	val = 0
	for i in arr:
		val += (i + 1) // 2
	if arr.count(1) == len(arr):
		print(-1)
	elif size == 3 and arr[0] % 2 == 1:
		print(-1)
	else:
		print(val)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = ans = 0
	mv = 0
	for i in range(1, n - 1):
		cnt += 1 * (arr[i] % 2 == 0)
		ans += arr[i] // 2 if arr[i] % 2 == 0 else (arr[i] + 1) // 2
		if arr[i] % 2:
			mv = max(mv, arr[i])
	if cnt > 0:
		return ans
	elif n == 3:
		return -1
	elif mv > 1:
		return ans
	else:
		return -1
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 3 and l[1] % 2 == 1 or sum(l[1:-1]) == n - 2:
		print(-1)
	elif n == 3 and l[1] == 2:
		print(1)
	else:
		count = 0
		sum_odd = 0
		steps = 0
		for i in l[1:-1]:
			if i % 2 == 1:
				count += 1
				sum_odd += i
		steps = (count + 1) // 2
		plus = 0
		if count % 2 == 0:
			plus = 1
		steps += (sum(l[1:-1]) + plus) // 2
		print(steps)


import math

def solve(n, a):
	if n == 3:
		if a[1] % 2 == 0:
			print(int(a[1] / 2))
		else:
			print(-1)
	else:
		b = a[1:-1]
		ans = 0
		noans = True
		for num in b:
			if num > 1 and noans:
				noans = False
			ans = ans + math.ceil(num / 2)
		if noans:
			print(-1)
		else:
			print(ans)
debugmode = 0
if debugmode:
	with open('input.txt', 'r') as f:
		t = int(f.readline())
		for _ in range(t):
			n = int(f.readline())
			a = list(map(int, f.readline().split()))
			solve(n, a)
else:
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		solve(n, a)


t = int(input())

def main():
	for _ in range(t):
		_ = int(input())
		arr = list(map(int, input().split()))
		arr = arr[1:-1]
		if len(arr) == 1 and arr[0] % 2 == 1:
			print(-1)
		elif sum(arr) == len(arr):
			print(-1)
		else:
			ans = 0
			for i in arr:
				ans += (i + 1) // 2
			print(ans)
main()


t = int(input())
for test_case in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.pop(0)
	a.pop(-1)
	if len(a) == 1 and a[0] % 2 == 1:
		print(-1)
	elif max(a) == 1:
		print(-1)
	else:
		print((sum(a) + len([True for i in a if i % 2 == 1])) // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	if n == 3 and lst[1] % 2 == 1:
		print(-1)
		continue
	areOnes = True
	for i in range(1, n - 1):
		if lst[i] != 1:
			areOnes = False
			break
	if areOnes:
		print(-1)
		continue
	res = 0
	for i in range(1, n - 1):
		res += (lst[i] + 1) // 2
	print(res)


def check_stones(numbers, length):
	number_of_bunch = length - 2
	if number_of_bunch == 1 and numbers[number_of_bunch] % 2 == 1:
		return -1
	if sum(numbers[1:-1]) == number_of_bunch:
		return -1
	number_of_moves = 0
	for i in numbers[1:-1]:
		number_of_moves += i // 2 + 1 if i % 2 == 1 else i // 2
	return number_of_moves

def main():
	number_of_test_cases = int(input())
	for _ in range(number_of_test_cases):
		num_length = int(input())
		numbers = list(map(int, input().split()))
		print(check_stones(numbers, num_length))
main()


def AbhiSolveKiya(n, a):
	even = 0
	odd = 0
	ops = 0
	ones = 0
	for i in range(1, n - 1):
		if a[i] == 1:
			ones += 1
		if a[i] & 1:
			odd += 1
			ops += (a[i] + 1) // 2
		else:
			even += 1
			ops += a[i] // 2
	if ones == n - 2:
		return -1
	if even == 0 and odd == 1:
		return -1
	return ops
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(AbhiSolveKiya(n, l))


t = int(input())
a = []
for i in range(t):
	input()
	a.append([int(i) for i in input().split(' ')])
for l in a:
	op = 0
	one = True
	for i in range(1, len(l) - 1):
		if one and l[i] != 1:
			one = False
		if l[i] % 2 == 0:
			op += l[i] / 2
		else:
			op += (l[i] + 1) / 2
	if len(l) - 2 == 1 and l[1] % 2 == 1 or one:
		op = -1
	print(int(op))


def count(values):
	if sum(values) == len(values):
		return -1
	if len(values) == 1 and values[0] % 2 == 1:
		return -1
	result = 0
	for i in values:
		result += i % 2
		result += i // 2
	return result
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	values = list(map(int, input().strip().split()))
	print(count(values[1:-1]))


for z in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	del l[0], l[-1]
	if n == 3:
		if l[0] % 2 == 0:
			print(l[0] // 2)
		else:
			print(-1)
	elif l.count(1) == n - 2:
		print(-1)
	else:
		odd = 0
		for i in l:
			if i % 2 != 0:
				odd += 1
		print(sum(l) // 2 + odd // 2 + odd % 2)


def minStones(arr):
	if len(arr) == 3 and arr[1] % 2 == 1:
		return -1
	flag = True
	for i in range(1, len(arr) - 1):
		if arr[i] != 1:
			flag = False
			break
	if flag:
		return -1
	s = 0
	for i in range(1, len(arr) - 1):
		n = arr[i]
		if n % 2 == 0:
			s += n // 2
		else:
			s += n // 2 + 1
	return s
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(minStones(arr))


def problem_c(n, m):
	total = 0
	flag = False
	even = 0
	odd = 0
	m.pop(0)
	m.pop(-1)
	for i in m:
		if flag == False:
			if i != 1:
				flag = True
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
		total += i
	if flag == False or (n == 1 and odd == 1):
		return -1
	elif odd == 0:
		return int(total / 2)
	elif even == 0:
		return int((total + n) / 2)
	elif even != 0 and odd != 0:
		return int((total + odd) / 2)
t = int(input())
for _ in range(t):
	print(problem_c(int(input()) - 2, [int(i) for i in input().split()]))


tc = int(input())
for _ in range(tc):
	n = int(input())
	v = list(map(int, input().split()))
	ok = False
	ans = 0
	for i in range(1, n - 1):
		t = (v[i] + 1) // 2
		ans += t
		if v[i] > 1:
			ok = True
	if not ok or (n == 3 and v[1] % 2 == 1):
		print('-1')
	else:
		print(ans)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	nums = nums[1:n - 1]
	if len(nums) == 1 and nums[0] % 2 == 1:
		print(-1)
		continue
	if sum(nums) == len(nums):
		print(-1)
		continue
	ans = 0
	for num in nums:
		if num % 2 == 1:
			ans += num // 2 + 1
		else:
			ans += num // 2
	print(ans)


import sys

def run():
	n = int(input())
	arr = list(map(int, input().split()))
	if all((arr[i] == 1 for i in range(1, n - 1))) or (n == 3 and arr[1] % 2 == 1):
		print(-1)
	else:
		ans = odds = 0
		for i in range(1, n - 1):
			ans += arr[i] // 2
			if arr[i] % 2:
				odds += 1
		print(ans + odds)

def main():
	t = int(input())
	for _ in range(t):
		run()
main()


t = int(input())
for it in range(t):
	n = int(input())
	a = [int(j) for j in input().split(' ')]
	(s, tt) = (0, 0)
	for i in a[1:-1]:
		if i == 1:
			tt += 1
		s += i - i // 2
	if tt == n - 2:
		print(-1)
	elif n == 3 and a[1] % 2 == 1:
		print(-1)
	else:
		print(s)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	temp = [1 for _ in range(n - 2)]
	if n == 3 and a[1] % 2 != 0 or a[1:n - 1] == temp:
		print('-1')
	else:
		count = 0
		for i in a[1:n - 1]:
			if i % 2 == 0:
				count += i // 2
			else:
				count += (i + 1) // 2
		print(count)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = l[1:n - 1]
	if n == 3:
		if l[1] % 2 != 0:
			print(-1)
		else:
			print(l[1] // 2)
	else:
		(sum, ctr) = (0, 0)
		valid = False
		for i in range(len(l1)):
			if l1[i] == 1:
				ctr += 1
				if ctr == n - 2:
					valid = True
					break
			sum += (l1[i] + 1) // 2
		if valid == True:
			print(-1)
		else:
			print(sum)


def calc(a, n):
	if n == 3 and a[1] & 1:
		return -1
	if all([a[i] == 1 for i in range(1, n - 1)]):
		return -1
	ans = 0
	for i in range(1, n - 1):
		ans += a[i] + 1 >> 1
	return ans
k = int(input())
while k:
	n = int(input())
	a = [int(i) for i in input().split()]
	print(calc(a, n))
	k -= 1


a = int(input())
for x in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	f = c[1:b - 1].count(1)
	n = 0
	if b == 3 and c[1] % 2 == 1:
		print(-1)
	elif f == b - 2:
		print(-1)
	else:
		for y in range(1, b - 1):
			n += (c[y] + 1) // 2
		print(n)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 3 and a[1] % 2 != 0 or a[1:n - 1].count(1) == n - 2:
		print(-1)
	else:
		sum = 0
		for j in range(1, n - 1):
			sum += (a[j] + 1) // 2
		print(sum)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(a) == 3 and a[1] & 1 or a[1:n - 1] == [1] * (n - 2):
		print(-1)
		continue
	s = 0
	for i in range(1, n - 1):
		if a[i] & 1:
			s = s + (a[i] + 1 >> 1)
		else:
			s = s + (a[i] >> 1)
	print(s)


for i in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	p = 0
	if n == 3 and s[1] % 2 != 0 or s[1:n - 1].count(1) == n - 2:
		p = -1
	else:
		for i in s[1:n - 1]:
			p += (i + 1) // 2
	print(p)


def solve():
	input()
	A = [int(x) for x in input().split()]
	A = A[1:-1]
	if len(A) == 1 and A[0] % 2 == 1:
		return -1
	(pairs, odd) = (0, 0)
	for x in A:
		pairs += x // 2
		odd += x % 2
	if pairs == 0 and odd > 0:
		return -1
	return pairs + odd
t = int(input())
for _ in range(t):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	numbers = list(map(int, input().split()))
	numbers.pop(0)
	numbers.pop(-1)
	ans = 0
	if max(numbers) == 1:
		ans = -1
	elif len(numbers) == 1 and numbers[0] % 2 != 0:
		ans = -1
	else:
		for item in numbers:
			ans += item // 2 + item % 2
	print(ans)


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	net = A[1:-1]
	if n == 3 and A[1] % 2 == 1:
		print(-1)
		return
	flag = 1
	count = 0
	for i in net:
		if i != 1:
			flag = 0
		count += ceil(i / 2)
	if flag:
		print(-1)
		return
	print(count)
t = int(input())
while t != 0:
	solve()
	t -= 1


n = int(input())
for test in range(n):
	(s, odd) = (0, 0)
	t = int(input())
	data = list(map(int, input().split()))
	for i in range(1, t - 1):
		odd += data[i] % 2
		s += data[i] // 2
	if odd and t == 3 or s == 0:
		print(-1)
		continue
	s += odd
	print(s)


def solve(a, n):
	if n == 3 and a[1] % 2 == 1:
		return -1
	flag = False
	ans = 0
	for i in range(1, n - 1):
		if a[i] > 1:
			flag = True
		if a[i] % 2 == 0:
			ans += a[i] // 2
		else:
			ans += (a[i] + 1) // 2
	if not flag:
		return -1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = solve(a, n)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 3 and a[1] % 2 or all((i == 1 for i in a[1:-1])):
		print(-1)
	else:
		ans = 0
		for i in a[1:-1]:
			ans += (i + 1) // 2
		print(ans)


for T in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	if len(arr) == 3 and arr[1] % 2 == 1 or max(arr[1:len(arr) - 1]) == 1:
		print(-1)
	else:
		c = 0
		for i in range(1, len(arr) - 1):
			c += (arr[i] + 1) // 2
		print(c)


for _ in [0] * int(input()):
	n = int(input())
	a = list(map(int, input().split()))[1:n - 1]
	p = s = 0
	for i in a:
		p = p + (i & 1)
		s = s + i
	if s == n - 2 or (n == 3 and s & 1 == 1):
		print(-1)
	else:
		print((s - p) // 2 + p)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if n == 3 and a[1] % 2:
		print(-1)
		continue
	(res, s) = (0, 0)
	for k in a[1:n - 1]:
		p = k % 2
		res += k // 2 + p
		s += k
	if s == n - 2:
		print(-1)
	else:
		print(res)


def func(n):
	n1 = 0
	for i in range(1, n + 1):
		j = 1
		s1 = 1
		while j <= i:
			s1 *= (n + 1 - j) / j
			j += 1
		n1 += s1
	return n1
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a1 = a[1:-1]
	if len(a1) == 1 and a1[0] % 2 == 1 or a1.count(1) == len(a1):
		print(-1)
	else:
		aa = sum(a1)
		for i in a1:
			aa += i % 2
		print(aa // 2)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	d = 0
	flag = True
	for i in range(1, n - 1):
		if a[i] % 2 == 1:
			c += 1
		if a[i] >= 2:
			flag = False
	if n == 3 and c == 1:
		print(-1)
		continue
	s = sum(a) - a[0] - a[-1] + c
	if flag:
		print(-1)
		continue
	print(s // 2)


t = int(input())

def h(l, n):
	if n < 4 and l[1] % 2 == 1:
		return False
	else:
		val = sum(l) - l[0] - l[n - 1]
		if val < n - 1:
			return False
		else:
			return True

def q(l, n):
	if h(l, n):
		s = 0
		for i in range(1, n - 1):
			s += (l[i] + 1) // 2
		return s
	else:
		return -1
for i in range(t):
	n = int(input())
	j = input().split()
	l = list(map(int, j))
	print(q(l, n))


for _ in range(int(input())):
	n = int(input())
	s = [int(i) for i in input().split()]
	s.pop(n - 1)
	s.pop(0)
	s.sort()
	ans = 0
	if len(s) == 1 and s[0] % 2 == 1 or s[n - 3] == 1:
		print(-1)
	else:
		for i in range(n - 2):
			if s[i] % 2 == 1:
				ans += (s[i] + 1) // 2
			else:
				ans += s[i] // 2
		print(ans)


for _ in range(int(input())):
	y = int(input())
	x = list(map(int, input().split()))
	z = 0
	if y == 3 and x[1] % 2 != 0:
		z = -1
	elif x[1:y - 1].count(1) == y - 2:
		z = -1
	else:
		for i in range(1, y - 1):
			if x[i] % 2 != 0:
				z += x[i] // 2 + 1
			else:
				z += x[i] // 2
	print(z)


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


def solve(a, n):
	flag = 0
	res = 0
	for i in range(1, n - 1):
		if a[i] % 2 == 1:
			res += (a[i] + 1) // 2
		else:
			res += a[i] // 2
			flag = 1
		if flag == 0 and a[i] >= 2 and (n > 3):
			flag = 1
	if flag:
		return res
	else:
		return -1
	return
t = int(input())
for i in range(1, t + 1):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a, n))


T = int(input())

def calc_op(l):
	cnt = 0
	for i in range(len(l)):
		if l[i] % 2 == 0:
			cnt += l[i] // 2
		else:
			cnt += l[i] // 2 + 1
	return cnt
for _ in range(T):
	N = int(input())
	l = list(map(int, input().split()))[1:-1]
	if len(l) == 1:
		if l[0] % 2 == 0:
			print(calc_op(l))
		else:
			print(-1)
	else:
		is_2_over_exists = False
		for i in l:
			if i >= 2:
				is_2_over_exists = True
				break
		if is_2_over_exists:
			print(calc_op(l))
		else:
			print(-1)


from math import *
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ok = True
	if n == 3:
		if a[1] % 2:
			print(-1)
			continue
	ans = 0
	for i in range(1, n - 1):
		ok = ok & (a[i] == 1)
		ans += ceil(a[i] / 2)
	if ok:
		print(-1)
	else:
		print(ans)


t = int(input())

def funk(tab):
	e = 0
	if n == 1 and tab[0] % 2 == 1:
		return -1
	for i in tab:
		if i > 1:
			break
	else:
		return -1
	for i in tab:
		e += int((i + 1) / 2)
	return e
for i in range(t):
	n = int(input())
	temp = input().split()
	tab = []
	for i in range(1, n - 1):
		tab.append(int(temp[i]))
	n -= 2
	print(funk(tab))


n = int(input())
for i in range(1, n + 1):
	a = int(input())
	nums = list(map(int, input().split()))
	cnt1 = 0
	cnt2 = 0
	ans = 0
	for j in range(1, a - 1):
		cnt2 = cnt2 + nums[j]
		if nums[j] % 2 == 1:
			cnt1 = cnt1 + 1
	ans = (cnt1 + cnt2) // 2
	k = 0
	if a == 3 and nums[1] % 2 == 1:
		k = 1
	if cnt1 == a - 2 and ans == a - 2:
		k = 1
	if k == 0:
		print(ans)
	if k == 1:
		print('-1')


def solve(arr, n):
	(cntone, res) = (0, 0)
	if n == 3:
		return -1 if arr[1] % 2 == 1 else arr[1] // 2
	for i in range(1, n - 1):
		if arr[i] == 1:
			cntone += 1
		res += (arr[i] + 1) // 2
	if cntone == n - 2:
		return -1
	return res
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(arr, n))
	t -= 1


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


def calc_op(n, a):
	ans = 0
	for i in range(1, n - 1):
		if a[i] % 2 == 0:
			ans += a[i] // 2
		else:
			ans += a[i] // 2 + 1
	return ans
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 3:
		if a[1] % 2 == 0:
			print(calc_op(n, a))
		else:
			print(-1)
	else:
		over_two = False
		for i in range(1, n - 1):
			if a[i] >= 2:
				over_two = True
				break
		if over_two:
			print(calc_op(n, a))
		else:
			print(-1)


n = int(input())
stone_num = []
stones = []
modify_index = []
ans = []
for i in range(n):
	stone_num.append(int(input()))
	stones.append(list(map(lambda x: int(x), input().split())))
	stones[i].pop(0)
	stones[i].pop(len(stones[i]) - 1)
for i in stones:
	index = 0
	modify_index_1 = []
	while index < len(i):
		if i[index] % 2 != 0:
			modify_index_1.append(index)
			i[index] += 1
		index += 1
	modify_index.append(modify_index_1)
j = 0
while j < len(stones):
	if len(modify_index[j]) == len(stones[j]) and max(stones[j]) == 2:
		ans.append(-1)
	elif len(modify_index[j]) == len(stones[j]) and len(modify_index[j]) == 1:
		ans.append(-1)
	else:
		ans_1 = 0
		all_stones = 0
		for k in range(len(stones[j])):
			all_stones += stones[j][k]
		ans_1 += int(all_stones / 2)
		ans.append(ans_1)
	j += 1
for i in ans:
	print(i)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[1:n - 1]
	ans = 0
	if n == 3 and a[1] % 2 == 1 or max(b) == 1:
		print(-1)
		continue
	for i in range(1, n - 1):
		ans += int((a[i] + 1) / 2)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(j) for j in input().split()]
	if n == 3 and a[1] % 2 == 1:
		print(-1)
		continue
	f = False
	ans = 0
	for i in range(1, n - 1):
		ans += (a[i] + 1) // 2
		if a[i] != 1:
			f = True
	if f is False:
		print(-1)
	else:
		print(ans)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	if n == 3 and l[1] % 2 != 0:
		ans = -1
	elif l[1:n - 1].count(1) == n - 2:
		ans = -1
	else:
		for i in range(1, n - 1):
			if l[i] % 2 == 0:
				ans += l[i] // 2
			else:
				ans += (l[i] + 1) // 2
	print(ans)
	t -= 1


import math
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(o, x) = (0, 0)
	for i in range(1, n - 1):
		if arr[i] % 2 == 0:
			x += arr[i] // 2
		else:
			o += 1
	if max(arr[1:n - 1]) == 1:
		print(-1)
		continue
	elif n == 3 and arr[1] % 2 != 0:
		print(-1)
		continue
	s = sum(arr[1:n - 1])
	s = s - o
	print(s // 2 + o)


for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	if max(arr[1:-1]) == 1:
		print(-1)
	elif N == 3 and arr[1] % 2:
		print(-1)
	else:
		for i in range(1, N - 1):
			ans += (arr[i] + 1) // 2
		print(ans)


for _ in range(int(input())):
	n = int(input())
	stones = list(map(int, input().split()))
	sub = stones[1:n - 1]
	if n == 3 and stones[1] % 2 == 1 or max(sub) == 1:
		print(-1)
		continue
	count = 0
	for i in range(1, n - 1):
		count += (stones[i] + 1) // 2
	print(count)


for _ in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	if n == 3 and k[1] % 2 == 1:
		print(-1)
		continue
	if sum(k[1:-1]) == n - 2:
		print(-1)
		continue
	ans = 0
	for x in k[1:-1]:
		ans += (x + 1) // 2
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	j = a[1:n - 1]
	k = len(j)
	val = 0
	for i in range(k):
		val += (j[i] + 1) // 2
	if j.count(1) == k:
		print('-1')
	elif n == 3 and j[0] % 2 == 1:
		print('-1')
	else:
		print(val)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	flag = True
	(ans, count) = (0, 0)
	if n == 3:
		if l[1] % 2 != 0:
			flag = False
	for i in range(1, n - 1):
		if l[i] == 1:
			count = count + 1
	if count == n - 2:
		flag = False
	for i in range(1, n - 1):
		if l[i] % 2 == 0:
			ans = ans + l[i] // 2
		else:
			ans = ans + (l[i] + 1) // 2
	if flag == False:
		print(-1)
	else:
		print(ans)


n = int(input())
for test in range(n):
	(d, jishuge) = (0, 0)
	t = int(input())
	data = list(map(int, input().split()))
	for i in range(1, t - 1):
		jishuge += data[i] % 2
		d += data[i] // 2
	if jishuge and t == 3 or d == 0:
		print(-1)
		continue
	print(d + jishuge)


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = a[1:n - 1]
	e = []
	o = []
	if len(a) == 1 and a[0] % 2 == 1:
		print(-1)
		continue
	for i in a:
		if i % 2 == 0:
			e += [i // 2]
		else:
			o += [i]
	cnt = sum(e)
	if cnt == 0 and max(o) == 1:
		print(-1)
		continue
	for i in o:
		cnt += (i + 1) // 2
	print(cnt)


t = int(input())
for e in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	se = 0
	no = 0
	for i in range(1, len(l1) - 1):
		if l1[i] % 2 == 0:
			se += l1[i]
		else:
			no += 1
			if l1[i] == 1:
				se += 1
			else:
				se += l1[i]
	if n == 3:
		if l1[1] % 2 == 0:
			print(int(l1[1] / 2))
		else:
			print(-1)
	elif se == n - 2:
		print(-1)
	else:
		q = int((se + no) / 2)
		print(q)


import math
import collections
import itertools
import functools

def fun(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	if len(a[1:n - 1]) == 1 and a[1] & 1:
		print('-1')
	elif sum(a[1:n - 1]) == n - 2:
		print('-1')
	else:
		ans = 0
		for x in a[1:n - 1]:
			ans += math.ceil(x / 2)
		print(ans)
for tc in range(int(input())):
	fun(tc)