Chef has an array A of size N. He can perform the following operation on A:
Select an i (1 ≤ i ≤ N) and for all 1 ≤ j ≤ i, set A_{j} := A_{j} + 1 (i.e. add 1 to every element in the prefix of length i).

Chef wants to convert A to a *palindrome* by using the above operation minimum number of times. Can you help Chef?  
If it is not possible to convert A to a *palindrome*, output -1.

Note: An array is called *palindrome* if it reads the same backwards and forwards, for e.g. [1, 4, 1] and [7, 3, 3, 7] are palindromic arrays.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the array A.
- The 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 required to convert A to a palindromic array. 

If it is not possible to do so, output -1.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 3 \cdot 10^{5}$
$1 ≤A_{i} ≤10^{9}$
- Sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
4 2 2 4
5
5 4 3 2 1
4
1 2 3 4

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

----- explanation 1 ------ 
Test case $1$: The given array is already a palindrome.

Test case $2$: It can be proven that it is not possible to convert $A$ to a palindromic array using the given operation.

Test case $3$: We can perform the following operations:
- Select $i = 1$, $[1, 2, 3, 4] \rightarrow [2, 2, 3, 4]$
- Select $i = 2$, $[2, 2, 3, 4] \rightarrow [3, 3, 3, 4]$
- Select $i = 1$, $[3, 3, 3, 4] \rightarrow [4, 3, 3, 4]$

Difficulty: MEDIUM
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	S = [int(x) for x in input().split()]
	dif = S[-1] - S[0]
	ans = True
	for i in range(int(n / 2)):
		if S[-i - 1] - S[i] > dif or S[-i - 1] - S[i] < 0:
			print(-1)
			ans = False
			break
		dif = S[-i - 1] - S[i]
	if ans:
		print(S[-1] - S[0])


t = int(input())
for i in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	x = n // 2
	d1 = A[n - 1] - A[0]
	d2 = 0
	ans = 1
	for j in range(x - 1):
		d2 = A[n - j - 2] - A[j + 1]
		if d2 < 0:
			ans = 0
			break
		elif d2 <= d1:
			d1 = d2
		else:
			ans = 0
			break
	if ans == 0:
		print(-1)
	else:
		print(A[n - 1] - A[0])


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	assert len(a) == n
	last_diff = 0
	for i in reversed(range(n // 2)):
		diff = a[n - 1 - i] - a[i]
		if diff < last_diff:
			diff = -1
			break
		last_diff = diff
	print(diff)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	bad = False
	tot = 0
	last_diff = 0
	for i in reversed(range(n // 2)):
		diff = a[n - 1 - i] - a[i]
		if diff < last_diff:
			diff = -1
			break
		last_diff = diff
	print(diff)


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	previous = num[-1] - num[0]
	for i in range(n // 2):
		current = num[-(i + 1)] - num[i]
		if current < 0 or previous < current:
			print(-1)
			break
		previous = current
	else:
		print(num[-1] - num[0])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = a[n - 1] - a[0]
	for i in range(n // 2):
		c = a[-(i + 1)] - a[i]
		if p < c or c < 0:
			print(-1)
			break
		p = c
	else:
		print(a[n - 1] - a[0])


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	diff = []
	for i in range(n // 2):
		diff.append(num[-(i + 1)] - num[i])
	if not all(map(lambda x: 1 if x >= 0 else 0, diff)):
		print(-1)
		continue
	for j in range(len(diff) - 1):
		if diff[j] < diff[j + 1]:
			print(-1)
			break
	else:
		print(diff[0])


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	half = n // 2
	left = a[:half]
	left.reverse()
	right = []
	if n % 2 == 1:
		right = a[half + 1:]
	else:
		right = a[half:]
	diff = []
	for i in range(half):
		diff.append(right[i] - left[i])
	check = diff[-1] < 0
	for i in range(half - 1):
		if diff[i] > diff[i + 1] or diff[i] < 0:
			check = True
			break
	if check:
		print(-1)
	else:
		print(diff[-1])


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	left = []
	k = True
	for i in range(len(a) // 2):
		if a[i] <= a[-i - 1]:
			left.append(a[-i - 1] - a[i])
		else:
			k = False
			print('-1')
			break
	if k:
		m = []
		m.extend(left)
		m.reverse()
		left.sort()
		if m == left:
			print(m[-1])
		else:
			print('-1')


for _ in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	m = N // 2
	l1 = l[:m]
	l1 = l1[::-1]
	l2 = l[m + 1:] if N & 1 else l[m:]
	cc = list()
	for i in range(len(l1)):
		cc.append(l2[i] - l1[i])
	fl = False
	for i in range(1, len(cc)):
		if cc[i] < cc[i - 1]:
			fl = True
	for v in cc:
		if v < 0:
			fl = True
	if fl:
		print(-1)
	else:
		print(cc[-1])


def palindrome(n, arr):
	if n == 1:
		return 0
	mid = (n - 1) // 2
	count = 0
	for i in range(mid, -1, -1):
		temp = arr[i] + count
		if temp > arr[n - 1 - i]:
			return -1
		elif temp < arr[n - 1 - i]:
			count += arr[n - 1 - i] - temp
	return count
t = int(input())
res = []
while t > 0:
	n = int(input())
	arr = [int(ele) for ele in input().split(' ')]
	res.append(palindrome(n, arr))
	t -= 1
for r in res:
	print(r)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a == a[::-1]:
		print('0')
		continue
	l = m = a[-1] - a[0]
	for i in range(n // 2):
		if a[i] > a[-i - 1]:
			print('-1')
			break
		if a[-i - 1] - a[i] > m:
			print('-1')
			break
		m = a[-i - 1] - a[i]
	else:
		print(l)


t = int(input())
for i in range(t):
	n = int(input())
	arr = input()
	arr = list(map(int, arr.split(' ')))
	if arr[0] > arr[-1]:
		print(-1)
		continue
	num_of_op = arr[-1] - arr[0]
	diff = arr[-1] - arr[0]
	j = -2
	flag = False
	for k in range(1, int(len(arr) / 2)):
		if arr[k] > arr[j] or diff < arr[j] - arr[k]:
			flag = True
			break
		diff = arr[j] - arr[k]
		j = j - 1
	if flag:
		num_of_op = -1
	print(num_of_op)


def give_result(num):
	i = 0
	j = len(num) - 1
	results = []
	same = 0
	while i < j:
		if num[i] != num[j]:
			if num[j] < num[i]:
				return -1
			else:
				if same != 0:
					return -1
				results.append(num[j] - num[i])
		else:
			same += 1
		i += 1
		j -= 1
	temp = results.copy()
	temp.sort(reverse=True)
	if len(results) > 0 and results == temp:
		return results[0]
	elif len(results) == 0:
		return 0
	else:
		return -1
for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	print(give_result(num))


from collections import Counter, defaultdict
import sys
import math

def sol(n, s):
	ans = 0
	if len(s) == 1 or len(s) == 0:
		return 0
	min_ = float('inf')
	for i in range(n // 2):
		if s[n - i - 1] < s[i]:
			return -1
		else:
			k = s[n - i - 1] - s[i]
			if k > min_:
				return -1
			else:
				min_ = s[n - i - 1] - s[i]
	return s[-1] - s[0]
input = sys.stdin.readline

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

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

def insr():
	return str(input())

def invr():
	return map(int, input().split())
T = inp()
for i in range(T):
	n = inp()
	s = inlt()
	print(sol(n, s))


t = int(input())

def pallindrome(a):
	d = len(a)
	q = 1
	for i in range(d // 2):
		if a[i] == a[d - i - 1]:
			continue
		else:
			q = 0
			break
	if not q:
		return 0
	else:
		return 1
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	if n % 2 == 1:
		a.pop(n // 2)
		n -= 1
	b = sorted(a)
	if pallindrome(a):
		print(0)
	else:
		j = 0
		d = a[n - 1] - a[0]
		while j < n // 2:
			if d >= a[n - j - 1] - a[j]:
				d = a[n - j - 1] - a[j]
				if d < 0:
					print(-1)
					break
			else:
				print(-1)
				break
			j += 1
		if j == n // 2:
			print(a[n - 1] - a[0])


for i in range(int(input())):
	n = int(input())
	pok = list(map(int, input().split()))
	mari = n // 2
	Flag = 0
	l1 = pok[:mari]
	l1 = l1[::-1]
	Flag = 1
	l2 = pok[mari + 1:] if n & 1 else pok[mari:]
	ihj = list()
	for j in range(len(l1)):
		ihj.append(l2[j] - l1[j])
		Flag += 1
	hyy = False
	for kj in range(1, len(ihj)):
		if ihj[kj] < ihj[kj - 1]:
			hyy = True
	for jh in ihj:
		if jh < 0:
			hyy = True
	if hyy:
		print(-1)
	else:
		print(ihj[-1])


for i in range(int(input())):
	f = int(input())
	arr = list(map(int, input().split()))
	fg = False
	answer = arr[f - 1] - arr[0]
	if answer < 0:
		print('-1')
		continue
	x = f // 2
	fin = answer
	for j in range(x):
		if arr[f - j - 1] >= arr[j]:
			if arr[f - j - 1] - arr[j] <= fin:
				fin = arr[f - j - 1] - arr[j]
			else:
				fg = True
				break
		else:
			fg = True
	if fg:
		print(-1)
	else:
		print(answer)


t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	i = 1
	j = N - 2
	F = 0
	L = []
	L.append(A[-1] - A[0])
	while i <= j:
		if A[i] > A[j]:
			F = 1
			break
		else:
			if A[j] - A[i] > L[-1]:
				F = 1
				break
			L.append(A[j] - A[i])
		i += 1
		j -= 1
	if F == 1:
		print(-1)
	else:
		print(L[0])


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 1
	j = n - 2
	flag = 0
	ans = []
	ans.append(arr[-1] - arr[0])
	while i <= j:
		if arr[i] > arr[j]:
			flag = 1
			break
		else:
			if arr[j] - arr[i] > ans[-1]:
				flag = 1
				break
			ans.append(arr[j] - arr[i])
		i += 1
		j -= 1
	if flag == 1:
		print(-1)
	else:
		print(ans[0])


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	half = len(A) // 2
	shortage = []
	possible = True
	prev = abs(A[-1] - A[0])
	for i in range(half):
		new = A[-i - 1] - A[i]
		possible = possible and (new <= prev and new >= 0)
		shortage.append(new)
		prev = new
	if possible:
		print(A[-1] - A[0])
	else:
		print(-1)


import numpy as np

def num_moves(l):
	maximum_value = max(l)
	number_moves = maximum_value
	for value in l:
		if value <= maximum_value:
			maximum_value = value
		else:
			return -1
	else:
		return number_moves
testcases = int(input())
for _ in range(testcases):
	N = int(input())
	A = list(map(lambda x: int(x), input().split(' ')))
	palindrome = []
	for (i, val) in enumerate(A):
		palindrome.append(max((A[i], A[-i - 1])))
	difference = list(np.subtract(np.array(palindrome), np.array(A)))
	print(num_moves(difference))


def helper(n, arr):
	(i, j) = (1, n - 2)
	diff = arr[-1] - arr[0]
	if diff < 0:
		return -1
	while i < j:
		if arr[j] - arr[i] < 0 or arr[j] - arr[i] > diff:
			return -1
		diff = arr[j] - arr[i]
		i += 1
		j -= 1
	return arr[-1] - arr[0]
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(helper(n, arr))


t = int(input())
for _ in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	r = n // 2
	count = 0
	if n % 2 == 0:
		temp1 = lis[:r]
		temp2 = lis[r:][::-1]
	else:
		temp1 = lis[:r]
		temp2 = lis[r + 1:][::-1]
	lis = []
	for i in range(r):
		a = temp2[i] - temp1[i]
		if abs(a) != a:
			print(-1)
			count = 1
			break
		else:
			lis.append(a)
	if count == 0:
		bro = lis.copy()
		bro.sort()
		bro = bro[::-1]
		if bro == lis:
			print(max(lis))
		else:
			print(-1)


t = input()
t = int(t)
while t:
	t = t - 1
	n = input()
	n = int(n)
	arr = input()
	arr = arr.split(' ')
	arr = list(map(int, arr))
	mid = (n - 1) // 2
	min_diff = None
	max_diff = None
	not_poss = False
	for i in range(mid + 1):
		diff = arr[n - 1 - i] - arr[i]
		if diff < 0:
			not_poss = True
			break
		if min_diff is None:
			min_diff = diff
		elif diff < min_diff:
			min_diff = diff
		elif diff > min_diff:
			not_poss = True
			break
		else:
			pass
		if max_diff is None:
			max_diff = diff
		else:
			max_diff = max(max_diff, diff)
	if not_poss:
		print('-1')
	else:
		print(max_diff)


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	b = True
	x = arr[0] - arr[-1]
	for i in range(0, n // 2):
		y = arr[i] - arr[-(i + 1)]
		if y > 0:
			b = False
			break
		if x > y:
			b = False
			break
		else:
			x = y
	if b == False:
		print(-1)
	else:
		print(arr[-1] - arr[0])


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))

	def solve():
		prev_diff = float('inf')
		for i in range(len(A) // 2):
			diff = A[len(A) - i - 1] - A[i]
			if diff < 0 or diff > prev_diff:
				return -1
			prev_diff = diff
		return A[-1] - A[0]
	print(solve())


try:
	for i in range(int(input())):
		n = int(input())
		A = list(map(int, input().split()))
		a1 = A[::-1]
		if A == a1:
			print(0)
		else:
			b = 0
			flag = True
			for j in range(1, n // 2):
				if A[j] > A[n - 1 - j]:
					print(-1)
					flag = False
					break
				if A[n - 1 - j] - A[j] > A[n - 1 - (j - 1)] - A[j - 1]:
					print(-1)
					flag = False
					break
			if flag:
				print(A[-1] - A[0])
except:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	flag = True
	for i in range(1, n // 2):
		if a[i] > a[n - 1 - i]:
			print(-1)
			flag = False
			break
		if a[n - 1 - i] - a[i] > a[n - 1 - (i - 1)] - a[i - 1]:
			print(-1)
			flag = False
			break
	if flag:
		print(abs(a[0] - a[n - 1]))


for i in range(int(input())):
	lenOfLst = int(input())
	lst = list(map(int, input().split()))
	mid = lenOfLst // 2
	vantageSection = lst[:mid][::-1]
	if lenOfLst % 2 == 0:
		secondSection = lst[mid:]
	else:
		secondSection = lst[mid + 1:]
	check = []
	for i in range(len(vantageSection)):
		check.append(secondSection[i] - vantageSection[i])
	impossible = False
	operations = check[-1]
	for i in range(1, len(check)):
		if check[i] < check[i - 1]:
			impossible = True
			break
	for i in check:
		if not impossible:
			if i < 0:
				impossible = True
			continue
		break
	if impossible:
		print(-1)
	else:
		print(operations)


t = int(input())
while t != 0:
	N = int(input())
	l = list(map(int, input().split()))
	m = N // 2
	l1 = l[:m]
	l1 = l1[::-1]
	l2 = l[m + 1:] if N & 1 else l[m:]
	l = []
	for i in range(len(l1)):
		l.append(l2[i] - l1[i])
	d = False
	for i in range(1, len(l)):
		if l[i] < l[i - 1]:
			d = True
	for j in l:
		if j < 0:
			d = True
	if d:
		print(-1)
	else:
		print(l[-1])
	t -= 1


T = int(input())
for _ in range(T):
	N = int(input())
	nums = list(map(int, input().split()))
	fstdif = nums[-1] - nums[0]
	if fstdif < 0:
		print(-1)
		continue
	lastdif = fstdif
	curdif = 0
	for i in range(1, N // 2):
		curdif = nums[-i - 1] - nums[i]
		if curdif < 0 or curdif > lastdif:
			print(-1)
			break
		else:
			lastdif = curdif
	if curdif == lastdif:
		print(fstdif)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	val = 0
	count = 0
	done = True
	for i in range(n // 2):
		if i == 0:
			val = l[n - 1] - l[0]
		else:
			ele = l[n - 1 - i] - l[i]
			if ele > val or ele < 0:
				done = False
				break
			else:
				val = ele
	if done:
		if n == 2 and val >= 0:
			print(val)
		elif n != 2:
			print(l[-1] - l[0])
		else:
			print(-1)
	else:
		print(-1)


for i in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	flag = False
	ans = arr[N - 1] - arr[0]
	if ans < 0:
		print('-1')
		continue
	x = N // 2
	final = ans
	for j in range(x):
		if arr[N - j - 1] >= arr[j]:
			if arr[N - j - 1] - arr[j] <= final:
				final = arr[N - j - 1] - arr[j]
			else:
				flag = True
				break
		else:
			flag = True
	if flag:
		print('-1')
	else:
		print(ans)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	mid = n // 2
	add = 0
	count = 0
	for i in range(mid - 1, -1, -1):
		if l[i] + add > l[n - i - 1]:
			print(-1)
			break
		elif l[i] + add == l[n - i - 1]:
			continue
		add += l[n - i - 1] - l[i] - add
	else:
		print(add)


def solution(arr, no_ele):
	if arr == arr[::-1]:
		return 0
	(i, j) = (0, no_ele - 1)
	temp = []
	while i < j:
		sb = arr[j] - arr[i]
		if sb < 0:
			return -1
		else:
			temp.append(sb)
		i += 1
		j -= 1
	ans = 0
	for i in range(len(temp) - 1, -1, -1):
		if ans > temp[i]:
			return -1
		temp1 = temp[i] - ans
		ans += temp1
	return ans
num = int(input())
for _ in range(num):
	no_ele = int(input())
	main_arr = list(map(int, input().strip().split()))
	print(solution(main_arr, no_ele))


def ans(l, n):
	mid = n // 2
	prev = 10 ** 9
	mx = -1
	for i in range(mid + 1):
		curr = l[n - i - 1] - l[i]
		if curr > prev:
			return -1
		mx = max(mx, curr)
		prev = curr
	return mx
t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	print(ans(l, n))


def mgc(arr, n):
	if arr == arr[::-1]:
		return 0
	temp = []
	for i in range(n // 2):
		x = arr[n - i - 1] - arr[i]
		if x < 0:
			return -1
		else:
			temp.append(x)
	ans = 0
	for i in range(len(temp) - 1, -1, -1):
		if ans > temp[i]:
			return -1
		ops = temp[i] - ans
		ans += ops
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(mgc(arr, n))


for j in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	count = 0
	flag = False
	for i in range(N // 2 - 1, -1, -1):
		if A[i] + count > A[N - i - 1]:
			flag = True
			break
		count += A[N - i - 1] - A[i] - count
	if flag == True:
		print(-1)
	else:
		print(count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	flag = 0
	sub = 0
	for i in range(n // 2, n):
		j = n - i - 1
		if l[i] >= l[j] + sub:
			sub = l[i] - l[j]
		else:
			flag = 1
			break
	if flag == 0:
		print(sub)
	else:
		print('-1')


t = int(input())
for _ in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	if N % 2 == 0:
		x = N // 2 - 1
	else:
		x = N // 2
	i = x
	flag = 0
	temp = 0
	moves = 0
	while i >= 0:
		if A[i] > A[N - i - 1]:
			flag = 1
			break
		else:
			moves = moves + A[N - i - 1] - A[i]
			temp = temp + A[N - i - 1] - A[i]
		if i > 0:
			A[i - 1] = A[i - 1] + temp
		i = i - 1
	if flag == 1:
		print(-1)
	else:
		print(moves)


def solve(n, arr):
	i = 0
	j = n - 1
	prevChange = float('inf')
	while i < j:
		if arr[i] == arr[j]:
			prevChange = 0
		elif arr[i] < arr[j] and arr[j] - arr[i] <= prevChange:
			prevChange = arr[j] - arr[i]
		else:
			return -1
		i += 1
		j -= 1
	return arr[-1] - arr[0]
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	possible = True
	to_add = []
	for i in range(n // 2):
		add = arr[-1 - i] - arr[i]
		if add < 0:
			possible = False
			break
		to_add.append(add)
	if possible:
		for i in range(n // 2 - 1):
			if to_add[i] < to_add[i + 1]:
				possible = False
				break
	if possible:
		print(to_add[0])
	else:
		print(-1)


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


t = int(input())
for i in range(t):
	n = int(input())
	c = n // 2
	f = 1
	r = 0
	l = [int(x) for x in input().split()]
	l1 = l[:c]
	l1 = l1[::-1]
	if n % 2 == 0:
		l2 = l[c:]
	else:
		l2 = l[c + 1:]
	for i in range(c):
		if l1[i] + r > l2[i]:
			f = 0
			break
		else:
			r += l2[i] - (l1[i] + r)
	if f == 0:
		print(-1)
	else:
		print(r)


import sys
input = sys.stdin.readline

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

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

def insr():
	return input().strip()

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))
ans = []
for _ in range(inp()):
	N = inp()
	A = inlt()
	c = N // 2
	if N == 1:
		ans.append(0)
		continue
	elif N <= 3:
		an = A[-1] - A[0] if A[0] <= A[-1] else -1
		ans.append(an)
		continue
	an = A[N - c] - A[c - 1]
	if an < 0:
		ans.append(-1)
		continue
	for i in range(c - 2, -1, -1):
		diff = A[-i - 1] - A[i]
		if diff < 0 or diff < an:
			an = -1
			break
		an = diff
	ans.append(an)
outplt(ans)


for _ in range(int(input())):
	l = int(input())
	s = list(map(int, input().split()))
	sl = s[:l // 2]
	sr = s[-(l // 2):][::-1]
	ss = [r - l for (l, r) in zip(sl, sr)]
	if sorted(ss, reverse=True) == ss and ss[-1] >= 0:
		print(ss[0])
	else:
		print('-1')


t = int(input())
while t > 0:
	s1 = int(input())
	a = list(map(int, input().split()))
	max1 = pow(10, 10)
	p = 0
	for i in range(s1 // 2):
		if -a[i] + a[s1 - 1 - i] >= 0 and -a[i] + a[s1 - 1 - i] <= max1:
			max1 = -a[i] + a[s1 - 1 - i]
		else:
			print(-1)
			break
	else:
		print(-a[0] + a[s1 - 1])
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	n //= 2
	l = 0
	flag = False
	for i in range(n - 1, -1, -1):
		m = a[-i - 1] - a[i] - l
		l += m
		if m < 0:
			print(-1)
			flag = True
			break
	if flag == False:
		print(l)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	j = n - 1
	a = []
	flag = 1
	while i < j:
		if l[i] > l[j]:
			print('-1')
			flag = 0
			break
		else:
			a.append(l[j] - l[i])
			i += 1
			j -= 1
	if flag:
		flag2 = 1
		for x in range(1, len(a)):
			if a[x] > a[x - 1]:
				print('-1')
				flag2 = 0
				break
		if flag2:
			print(max(a))


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	flag = False
	f = 0
	maxop = lst[n - 1] - lst[0]
	if maxop < 0:
		print('-1')
		continue
	m = n // 2
	p = maxop
	for j in range(m):
		if lst[n - j - 1] >= lst[j]:
			if lst[n - j - 1] - lst[j] <= p:
				p = lst[n - j - 1] - lst[j]
				pass
			else:
				flag = True
				break
		else:
			flag = True
	if flag:
		print('-1')
	else:
		print(maxop)


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


for i in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	flag = 0
	sub = 0
	for i in range(N // 2, N):
		j = N - i - 1
		if arr[i] >= arr[j] + sub:
			sub = arr[i] - arr[j]
		else:
			flag = 1
			break
	if flag == 0:
		print(sub)
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	l = (len(ar) - 1) // 2
	if len(ar) % 2 != 0:
		r = l
	else:
		r = l + 1
	diff = 0
	c = 0
	carry = 0
	flag = True
	while l != -1:
		ar[l] += carry
		if ar[r] > ar[l]:
			diff = ar[r] - ar[l]
			carry += diff
			c += diff
		elif ar[r] == ar[l]:
			pass
		else:
			flag = False
			break
		l -= 1
		r += 1
	if flag:
		print(c)
	else:
		print('-1')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print('0')
	else:
		flag = 0
		k = len(a) // 2
		b = []
		d = []
		count = 0
		for j in range(k):
			c = a[n - j - 1] - a[j]
			if c < 0:
				flag = 1
			b.append(c)
			d.append(c)
		d.sort()
		d = d[::-1]
		for j in range(k):
			if b[j] == d[j]:
				count = count + 1
		if count == k and flag == 0:
			print(max(b))
		else:
			print('-1')


for j in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[:int(n // 2) - 1:-1]
	l = 0
	v = 0
	i = n // 2 - 1
	flag = True
	while i >= 0:
		d = b[i] - a[i]
		if d < l:
			flag = False
		else:
			v = v + (d - l)
			l = d
		i -= 1
	if flag == True:
		print(v)
	else:
		print(-1)


A = int(input())
I = 0
while I < A:
	q = input()
	z = list(map(int, input().split()))
	Z = z.copy()
	start = z[0]
	end = z[len(z) - 1]
	if start == end:
		Z.reverse()
		if z == Z:
			print(0)
		else:
			print(-1)
	elif end < start:
		print(-1)
	else:
		if len(z) % 2 == 0:
			list1 = z[0:int(len(z) / 2):1]
			list2 = z[int(len(z) / 2)::1]
		else:
			list1 = z[0:int(len(z) / 2):1]
			list2 = z[int(len(z) / 2) + 1::1]
		if list1 == list2:
			print(-1)
		else:
			list2.reverse()
			subtracted = list()
			for (item1, item2) in zip(list1, list2):
				item = item2 - item1
				subtracted.append(item)
			m = subtracted
			n = sorted(subtracted, reverse=True)
			if m == n:
				flag = True
				for nume in m:
					if nume < 0:
						flag = False
						break
				if flag == True:
					print(m[0])
				else:
					print(-1)
			else:
				print(-1)
	I += 1


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


for t in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	C = 0
	B = N // 2 - 1
	Flag = False
	for i in range(B, -1, -1):
		C = A[N - i - 1] - A[i] - C
		if C < 0:
			Flag = True
		C = A[N - i - 1] - A[i]
	if Flag == True:
		print(-1)
	else:
		print(C)