You are given an array $a$ consisting of $n$ integers. The array is sorted if $a_1 \le a_2 \le \dots \le a_n$.

You want to make the array $a$ sorted by applying the following operation exactly once:

choose an integer $x$, then for every $i \in [1, n]$, replace $a_i$ by $|a_i - x|$.

Find any value of $x$ that will make the array sorted, or report that there is no such value.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases.

Each test case consists of two lines. The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$). The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^8$).

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print any integer $x$ ($0 \le x \le 10^9$) that makes the array sorted. It can be shown that if such an integer $x$ exists, there is at least one such integer between $0$ and $10^9$.

If there is no such integer, then print $-1$. If there are multiple suitable values of $x$, print any of them.


-----Examples-----

Input
8
5
5 3 3 3 5
4
5 3 4 5
8
1 2 3 4 5 6 7 8
6
10 5 4 3 2 1
3
3 3 1
3
42 43 42
2
100000000 99999999
6
29613295 52036613 75100585 78027446 81409090 73215
Output
4
-1
0
42
2
-1
100000000
40741153


-----Note-----

In the first test case, after using $x = 4$, the array becomes $[1, 1, 1, 1, 1]$.

In the third test case, after using $x = 0$, the array becomes $[1, 2, 3, 4, 5, 6, 7, 8]$.

In the fourth test case, after using $x = 42$, the array becomes $[32, 37, 38, 39, 40, 41]$.

Source: codeforces | Difficulty: MEDIUM
Tags: Mathematics

Constructive algorithms


Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	INF = 10 ** 18
	l = 0
	r = 10 ** 9
	for i in range(1, n):
		(u, v) = (a[i - 1], a[i])
		if u < v:
			L = -INF
			R = (u + v) // 2
		elif u > v:
			L = (u + v + 1) // 2
			R = INF
		else:
			L = -INF
			R = INF
		(l, r) = (max(l, L), min(r, R))
	if l <= r:
		print(l)
	else:
		print(-1)

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


import heapq
import sys
import math
import itertools
from io import BytesIO, IOBase
import os
from math import *
input = sys.stdin.readline

def test(l):
	for i in range(1, len(l)):
		if l[i] < l[i - 1]:
			return False
	return True

def solve():
	n = int(input())
	l = [int(i) for i in input().split()]
	mx = -float('inf')
	for i in range(n - 1):
		if l[i + 1] < l[i]:
			mx = max(mx, ceil((l[i + 1] + l[i]) / 2))
	for i in range(n):
		l[i] = abs(l[i] - mx)
	if mx == -float('inf'):
		print(0)
	elif test(l):
		print(mx)
	else:
		print(-1)
for i in range(int(input())):
	solve()


import sys
import math

def main():
	num = int(sys.stdin.readline().strip())
	for l in range(num):
		sys.stdin.readline()
		arr = sys.stdin.readline().strip().split()
		inty = [int(x) for x in arr]
		maxAllowed = max(inty)
		minNeeded = 0
		for i in range(len(inty) - 1):
			if inty[i] < inty[i + 1]:
				a = (inty[i] + inty[i + 1]) // 2
				if a < maxAllowed:
					maxAllowed = a
			if inty[i] > inty[i + 1]:
				b = math.ceil((inty[i] + inty[i + 1]) / 2)
				if b > minNeeded:
					minNeeded = b
		if minNeeded > maxAllowed:
			print(-1)
		else:
			print(minNeeded)
main()


import math
import heapq
from collections import *
import sys
input = sys.stdin.readline

def fun(l, n):
	x = 0
	y = 99999999999
	for i in range(n - 1):
		if l[i] == l[i + 1]:
			continue
		if l[i] > l[i + 1]:
			if (l[i] + l[i + 1]) % 2 == 1:
				a = (l[i] + l[i + 1]) // 2 + 1
			else:
				a = (l[i] + l[i + 1]) // 2
			x = max(x, a)
		else:
			y = min(y, (l[i] + l[i + 1]) // 2)
	if x > y:
		print(-1)
	else:
		print(int(x))
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	fun(l, n)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(N, A) = (int(input()), list(map(int, input().split())))
	L = 0
	R = int(1000000000.0)
	for i in range(1, N):
		if A[i - 1] > A[i]:
			L = max(L, (A[i] + A[i - 1] + 1) // 2)
		elif A[i - 1] < A[i]:
			R = min(R, (A[i] + A[i - 1]) // 2)
	if R < L:
		print(-1)
	else:
		print(L)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	datas = list(map(int, input().split()))
	ans_min = 0
	ans_max = 10 ** 9
	Ispos = 1
	for i in range(n - 1):
		if datas[i] < datas[i + 1]:
			tmp = (datas[i] + datas[i + 1]) // 2
			if ans_min > tmp:
				Ispos = 0
				break
			ans_max = min(ans_max, tmp)
		elif datas[i] > datas[i + 1]:
			tmp = (datas[i] + datas[i + 1] + 1) // 2
			if ans_max < tmp:
				Ispos = 0
				break
			ans_min = max(ans_min, tmp)
	if Ispos == 0:
		print(-1)
	else:
		print(ans_min)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	h = 1000000000
	for j in range(n - 1):
		if a[j] > a[j + 1]:
			l = max(l, (a[j] + a[j + 1] + 1) // 2)
		elif a[j] < a[j + 1]:
			h = min(h, (a[j] + a[j + 1]) // 2)
	if l > h:
		print(-1)
	else:
		print(l)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	minn = 0
	maxx = 1000000000
	for i in range(n - 1):
		x = a[i]
		y = a[i + 1]
		midl = (x + y) // 2
		midr = (x + y + 1) // 2
		if x < y:
			maxx = min(maxx, midl)
		elif x > y:
			minn = max(minn, midr)
	if minn <= maxx:
		print(minn)
	else:
		print(-1)


import sys
for i in range(int(sys.stdin.readline())):
	l = int(sys.stdin.readline())
	ls = [int(a) for a in sys.stdin.readline().split()]
	ansmaybe = 0
	p = 1
	while p < l:
		if ls[p] < ls[p - 1]:
			ansmaybe = max(ansmaybe, (ls[p] + ls[p - 1] + 1) // 2)
			p += 1
			continue
		p += 1
	newls = [max(j - ansmaybe, ansmaybe - j) for j in ls]
	f = True
	for k in range(1, l):
		if newls[k] < newls[k - 1]:
			f = False
			break
	if f:
		print(ansmaybe)
		continue
	print('-1')


t = int(input())

def findX(arr):
	pre = arr[0]
	xinf = 0
	xmax = 100000000000
	for (i, a) in enumerate(arr):
		if a < pre:
			xinf = max(a + (pre - a + 1) // 2, xinf)
		if a > pre:
			xmax = min(pre + (a - pre) // 2, xmax)
		pre = a
	return None if xinf > xmax else xinf

def apply(arr, x):
	return [abs(a - x) for a in arr]
for _ in range(t):
	n = int(input())
	arr = [int(v) for v in input().split()]
	x = findX(arr)
	if x != None:
		print(x)
	else:
		print(-1)


t = int(input())
results = []
for i in range(t):
	n = int(input())
	nums = list(map(int, input().strip().split()))
	min_k = 0
	max_k = 0
	for j in range(n - 1):
		a = nums[j]
		b = nums[j + 1]
		if a == b:
			continue
		elif a > b:
			diff = a - b
			if diff % 2 == 1:
				need = b + diff // 2 + 1
			else:
				need = b + diff // 2
			min_k = max(min_k, need)
		else:
			diff = b - a
			if diff % 2 == 1:
				need = a + diff // 2
			else:
				need = a + diff // 2
			if max_k == 0:
				max_k = need
			else:
				max_k = min(max_k, need)
	if max_k == 0:
		results.append(min_k)
	elif min_k > max_k:
		results.append(-1)
	else:
		results.append(min_k)
for k in results:
	print(k)


def main():
	n = int(input())
	array = [int(el) for el in input().split()]
	(left, right) = (0, 10 ** 9)
	ans = -1
	for i in range(n - 1):
		(a, b) = (array[i], array[i + 1])
		new = (a + b) / 2
		if a < b:
			right = min(right, new)
		elif a > b:
			left = max(left, new)
	if left <= right and (int(left) == left or right - left >= 0.5):
		ans = int(left) if int(left) == left else int(left + 0.5)
	print(ans)
t = int(input())
for _ in range(t):
	main()


import math

def ans(n, a):
	r = []
	if a == sorted(a):
		return 0
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			k = a[i] + a[i + 1]
			k = int(math.ceil(k / 2))
			r.append(k)
	z = max(r)
	for i in range(n):
		a[i] = abs(a[i] - z)
	if a == sorted(a):
		return z
	else:
		return -1
t = int(input())
l = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l.append(ans(n, a))
for i in range(t):
	print(l[i])


import math
n = int(input())
for _ in range(n):
	input()
	vals = list(map(int, input().split()))
	(minn, maxx) = (0, 10 ** 9)
	for (a, b) in zip(vals, vals[1:]):
		if a < b:
			maxx = min(maxx, (a + b) / 2)
		elif a > b:
			minn = max(minn, (a + b) / 2)
	if math.ceil(minn) <= math.floor(maxx):
		print(math.ceil(minn))
	else:
		print('-1')


def solve(numbers):
	answer = [0, 10 ** 9]
	for (index, num0) in enumerate(numbers[:-1]):
		num1 = numbers[index + 1]
		if num0 == num1:
			continue
		if num0 < num1:
			answer[1] = min(answer[1], num0 + (num1 - num0) // 2)
		else:
			answer[0] = max(answer[0], num1 + (num0 - num1 + 1) // 2)
	return -1 if answer[0] > answer[1] else answer[0]
for _ in range(int(input())):
	input()
	print(solve(list(map(int, input().split()))))


import math
t = int(input())
while t > 0:
	n = int(input())
	L = list(map(int, input().split()))
	MIN = 0
	MAX = 10 ** 9 + 1
	pre = L[0]
	for i in L[1:]:
		if i > pre:
			MAX = min(MAX, (pre + i) / 2)
		elif i < pre:
			MIN = max(MIN, (pre + i) / 2)
		pre = i
	MAX = int(MAX)
	MIN = math.ceil(MIN)
	if MIN <= MAX:
		print(MIN)
	else:
		print(-1)
	t -= 1


def solve(arr):
	(start, end) = (0, 10 ** 9)
	for i in range(1, len(arr)):
		if arr[i - 1] == arr[i]:
			continue
		if arr[i - 1] > arr[i]:
			tmp = (arr[i - 1] + arr[i] + 1) // 2
			start = max(start, tmp)
		else:
			tmp = (arr[i - 1] + arr[i]) // 2
			end = min(end, tmp)
	if end < start:
		print(-1)
	else:
		print(start)
T = int(input())
for test in range(T):
	input()
	solve(list(map(int, input().split())))


for _ in range(int(input())):
	l = 0
	r = 10 ** 9
	x = int(input())
	a = list(map(int, input().split()))
	for i in range(x - 1):
		y = a[i]
		z = a[i + 1]
		if y > z:
			l = max(l, (z + y + 1) // 2)
		elif y < z:
			r = min(r, (z + y) // 2)
	if l <= r:
		print(l)
	else:
		print(-1)


from typing import List
from bisect import *
from collections import *
from functools import *
from itertools import *
from math import *
from queue import PriorityQueue
INF = 2 ** 64 - 1
MOD = 10 ** 9 + 7
mi = lambda : map(int, input().split())
li = lambda : list(mi())

def main(n, nums):
	re = [0, INF]
	for i in range(1, n):
		a = nums[i - 1]
		b = nums[i]
		if a < b:
			re[1] = min(re[1], (a + b) // 2)
		elif a > b:
			re[0] = max(re[0], (a + b + 1) // 2)
		if re[0] > re[1]:
			print(-1)
			return
	print(re[0])
	return
caseNum = int(input())
for i in range(0, caseNum):
	n = int(input())
	nums = li()
	main(n, nums)


for k in range(int(input())):
	left = 0
	right = 10 ** 9
	j = int(input())
	a = tuple(map(int, input().split()))
	for i in range(j - 1):
		x = a[i]
		y = a[i + 1]
		if x > y:
			left = max(left, (y + x + 1) // 2)
		elif x < y:
			right = min(right, (y + x) // 2)
	if left <= right:
		print(left)
	else:
		print(-1)


n = int(input())
for i in range(n):
	t = int(input())
	a = list(map(int, input().split()))
	bolshe = []
	menshe = []
	for j in range(len(a) - 1):
		if a[j + 1] > a[j]:
			menshe.append((a[j] + a[j + 1]) // 2)
		elif a[j] > a[j + 1]:
			bolshe.append((a[j] + a[j + 1] + 1) // 2)
	Mbol = max(bolshe) if len(bolshe) != 0 else int(0)
	Mmen = min(menshe) if len(menshe) != 0 else int(1000000000.0)
	if Mbol > Mmen:
		print(-1)
	else:
		print(Mbol)


def solve(arr):
	lb = 0
	ub = 10 ** 9
	for i in range(1, len(arr)):
		if arr[i - 1] < arr[i]:
			ub = min(ub, (arr[i - 1] + arr[i]) // 2)
		elif arr[i - 1] > arr[i]:
			lb = max(lb, (arr[i - 1] + arr[i]) // 2 + (arr[i - 1] + arr[i]) % 2)
		if lb > ub:
			return -1
	return lb
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(arr))


num_case = int(input())
for case_idx in range(num_case):
	n = int(input())
	a = list(map(int, input().split()))

	def solve(n, a):
		lb = 0
		ub = 10 ** 9
		for i in range(1, n):
			if a[i - 1] > a[i]:
				lb = max(lb, (a[i - 1] + a[i] + 1) // 2)
			elif a[i - 1] < a[i]:
				ub = min(ub, (a[i - 1] + a[i]) // 2)
		return lb if lb <= ub else -1
	print(solve(n, a))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(mn, mx) = (0, 10 ** 9)
	for i in range(1, n):
		if a[i - 1] < a[i]:
			mx = min(mx, (a[i - 1] + a[i]) // 2)
		elif a[i - 1] > a[i]:
			mn = max(mn, (a[i - 1] + a[i] + 1) // 2)
	print(mn if mn <= mx else -1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	prev = arr[0]
	(large, small) = (float('inf'), 0)
	for i in range(1, n):
		if arr[i] > prev:
			large = min(large, (arr[i] + prev) // 2)
		elif arr[i] < prev:
			small = max(small, (arr[i] + prev + 1) // 2)
		prev = arr[i]
	if small > large:
		print(-1)
	else:
		print(small)


import math
import sys
for _ in range(int(input())):
	l = int(input())
	nums = list(map(int, input().split()))
	(mn, mx) = (0, sys.maxsize)
	for i in range(len(nums) - 1):
		x = nums[i]
		y = nums[i + 1]
		if x < y:
			mx = min(mx, (x + y) // 2)
		elif x > y:
			mn = max(mn, (x + y + 1) // 2)
	if mn <= mx:
		print(mn)
	else:
		print(-1)


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	up = 10 ** 9
	down = 0
	for i in range(n - 1):
		if arr[i] < arr[i + 1]:
			up = min(up, (arr[i] + arr[i + 1]) // 2)
		elif arr[i] > arr[i + 1]:
			down = max(down, (arr[i] + arr[i + 1] + 1) // 2)
	if down > up:
		print(-1)
	else:
		print(down)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(a, b) = (0, 10 ** 9)
	for i in range(1, n):
		if l[i] > l[i - 1]:
			b = min((l[i] + l[i - 1]) // 2, b)
		elif l[i] < l[i - 1]:
			a = max(a, ceil((l[i] + l[i - 1]) / 2))
			if a > b:
				break
	print(-1 if a > b else a)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ran = [0, float('inf')]
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			tempd = -((arr[i] + arr[i + 1]) // -2)
			if tempd > ran[0]:
				ran[0] = tempd
		elif arr[i] < arr[i + 1]:
			tempi = (arr[i] + arr[i + 1]) // 2
			if tempi < ran[1]:
				ran[1] = tempi
	print(ran[0] if ran[0] <= ran[1] else -1)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	min_tmp = 1000000000
	max_tmp = 0
	for j in range(len(a) - 1):
		if a[j] < a[j + 1]:
			tmp = int((a[j] + a[j + 1]) / 2)
			if min_tmp > tmp:
				min_tmp = tmp
		elif a[j] > a[j + 1]:
			tmp = math.ceil((a[j] + a[j + 1]) / 2)
			if max_tmp < tmp:
				max_tmp = tmp
	if max_tmp > min_tmp:
		print(-1)
	else:
		print(max_tmp)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans_min = 0
	ans_max = 10 ** 9
	for x in range(1, n):
		if arr[x] > arr[x - 1]:
			ans_max = min(ans_max, (arr[x] + arr[x - 1]) // 2)
		elif arr[x] < arr[x - 1]:
			ans_min = max(ans_min, (arr[x] + arr[x - 1] + 1) // 2)
	if ans_min > ans_max:
		print(-1)
		continue
	print(ans_min)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(l, r) = (0, 10 ** 9)
	for i in range(1, len(a)):
		if a[i - 1] < a[i]:
			r = min(r, (a[i - 1] + a[i]) // 2)
		elif a[i - 1] > a[i]:
			l = max(l, (a[i - 1] + a[i] + 1) // 2)
	if l <= r:
		print(l)
	else:
		print(-1)


import math
t = int(input())
for i in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	minx = 0
	maxx = 1000000000.0
	for i in range(len(L) - 1):
		if L[i] < L[i + 1]:
			x1 = (L[i] + L[i + 1]) // 2
			if maxx > x1:
				maxx = x1
		elif L[i] > L[i + 1]:
			x2 = math.ceil((L[i] + L[i + 1]) / 2)
			if minx < x2:
				minx = x2
	if maxx >= minx:
		print(minx)
	else:
		print(-1)


for _ in range(int(input())):
	i = int(input())
	numbers = [int(b) for b in input().split()]
	c = []
	upperc = 10 ** 9 + 1
	lowerc = 0
	for i in range(len(numbers) - 1):
		if numbers[i] > numbers[i + 1]:
			thing = (numbers[i + 1] + numbers[i] - 1) // 2 + 1
			if upperc - lowerc >= 0:
				if thing > lowerc:
					lowerc = thing
			else:
				break
		elif numbers[i] < numbers[i + 1]:
			thing = (numbers[i + 1] + numbers[i]) // 2
			if upperc - lowerc >= 0:
				if thing < upperc:
					upperc = thing
			else:
				break
	if upperc - lowerc >= 0:
		print(lowerc)
	else:
		print(-1)


def get_int():
	return int(input())

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

def main():
	test = get_int()
	for _ in range(test):
		n = get_int()
		nums = get_nums()
		mx = float('inf')
		mn = 0
		for index in range(n - 1):
			x = nums[index]
			y = nums[index + 1]
			midLeft = (nums[index] + nums[index + 1]) // 2
			midRight = (nums[index] + nums[index + 1] + 1) // 2
			if x < y:
				mx = min(mx, midLeft)
			if x > y:
				mn = max(mn, midRight)
		if mn <= mx:
			print(mn)
		else:
			print(-1)
main()


t = int(input(''))
for i in range(t):
	n = int(input(''))
	l = input('').split(' ')
	l = [int(x) for x in l]
	left = 0
	right = 10 ** 9
	for j in range(n - 1):
		a = l[j]
		b = l[j + 1]
		if a == b:
			continue
		if a < b:
			mid = (a + b) // 2
			if right == -1:
				right = mid + 1
			else:
				right = min(right, mid + 1)
		if a > b:
			mid = (a + b + 1) // 2
			left = max(left, mid)
		if left >= right:
			break
	if left < right:
		print(left)
	else:
		print(-1)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	list = [int(x) for x in input().split()]
	l = 0
	r = 10 ** 9
	for i in range(1, len(list)):
		if list[i] > list[i - 1]:
			r = min((list[i] + list[i - 1]) // 2, r)
		if list[i] < list[i - 1]:
			l = max((list[i] + list[i - 1] + 1) // 2, l)
	if l > r:
		print(-1)
	else:
		print(l)


def calc():
	n = int(input())
	arr = [int(el) for el in input().split()]
	(mx, mn) = (10000000000.0, -1)
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			continue
		if arr[i] < arr[i + 1]:
			mx = min(mx, (arr[i] + arr[i + 1]) // 2)
		else:
			mn = max(mn, (arr[i] + arr[i + 1] + 1) // 2)
	if mx < mn:
		print(-1)
	else:
		print(max(mn, 0))
for _ in range(int(input())):
	calc()


t = int(input())
for tes in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = int(0)
	r = int(1000000000.0)
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			l = max(l, (a[i] + a[i + 1] + 1) // 2)
		elif a[i] < a[i + 1]:
			r = min(r, (a[i] + a[i + 1]) // 2)
	ans = l
	if l > r:
		ans = -1
	print(ans)


t = int(input())
for t_ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = 1000000000
	s = 0
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			s = max((a[i] + a[i + 1]) / 2, s)
		elif a[i] < a[i + 1]:
			l = min((a[i] + a[i + 1]) / 2, l)
	s = int((2 * s + 1) // 2)
	l = int(2 * l // 2)
	if s <= l:
		print(s)
	else:
		print(-1)


from collections import defaultdict
from math import ceil, floor
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	upper = [1000000000]
	lower = [0]
	for j in range(n - 1):
		x = (l[j] + l[j + 1]) / 2
		if l[j] > l[j + 1]:
			lower.append(ceil(x))
		elif l[j] < l[j + 1]:
			upper.append(floor(x))
	if min(upper) < max(lower):
		print(-1)
	else:
		print(max(lower))


import math

def isGood(arr):
	for i in range(1, len(arr)):
		if arr[i] < arr[i - 1]:
			return False
	return True

def solve():
	n = int(input())
	arr = list(map(int, input().split(' ')))
	x = -1
	for i in range(1, len(arr)):
		if arr[i] < arr[i - 1]:
			y = math.ceil((arr[i] + arr[i - 1]) / 2)
			x = max(y, x)
	if x == -1:
		print(0)
		return
	q = [abs(b - x) for b in arr]
	if isGood(q):
		print(x)
	else:
		print(-1)
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	inf = 1000000000
	ans = [0, inf]
	for i in range(n - 1):
		if l[i] > l[i + 1]:
			if ans[0] < l[i] + l[i + 1] - (l[i] + l[i + 1]) // 2:
				ans[0] = l[i] + l[i + 1] - (l[i] + l[i + 1]) // 2
		elif l[i] == l[i + 1]:
			pass
		elif ans[1] > (l[i] + l[i + 1]) // 2:
			ans[1] = (l[i] + l[i + 1]) // 2
	if ans[0] <= ans[1]:
		print(ans[0])
	else:
		print(-1)


import math
t = int(input())
for _ in range(t):
	max_left = 0
	max_right = int(1000000000.0) + 200
	n = int(input())
	tab = list(map(int, input().split()))
	for i in range(n - 1):
		(e1, e2) = tab[i:i + 2]
		if e1 < e2:
			max_right = min((e2 + e1) / 2, max_right)
		elif e1 > e2:
			max_left = max((e1 + e2) / 2, max_left)
	if max_left <= max_right:
		if max_left == max_right and round(max_left) != max_left:
			print(-1)
		else:
			print(math.ceil(max_left))
	else:
		print(-1)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	r = 1000000000
	for i in range(1, n):
		if a[i] > a[i - 1]:
			r = min(r, (a[i - 1] + a[i]) // 2)
		elif a[i] < a[i - 1]:
			l = max(l, ceil((a[i - 1] + a[i]) / 2))
	if l > r:
		print(-1)
	else:
		print(l)


t = int(input())
for _ in range(t):
	n = int(input())
	(*a,) = map(int, input().split())
	max_x = max(a) + 100
	min_x = -1
	for i in range(n - 1):
		if a[i] < a[i + 1]:
			max_x = min(max_x, (a[i] + a[i + 1]) // 2)
		elif a[i] > a[i + 1]:
			min_x = max(min_x, (a[i] + a[i + 1]) // 2 + (a[i] + a[i + 1]) % 2)
	if max_x < min_x:
		ans = -1
	else:
		ans = max(0, min_x)
	print(ans)


for t in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	(mn, mx) = (0, 10 ** 9)
	for i in range(0, len(arr) - 1):
		s = arr[i] + arr[i + 1]
		if arr[i] > arr[i + 1]:
			mn = max(mn, (s + 1) // 2)
		elif arr[i] < arr[i + 1]:
			mx = min(mx, s // 2)
		if mn > mx:
			break
	print(mn if mn <= mx else -1)


n = int(input())
for i in range(n):
	m = int(input())
	lst = list(map(int, input().split()))
	biggest = 0
	for j in range(m - 1):
		if lst[j] > lst[j + 1]:
			biggest = max(biggest, (lst[j + 1] + lst[j] + 1) // 2)
	can = True
	for j in range(m - 1):
		if abs(lst[j] - biggest) > abs(lst[j + 1] - biggest):
			can = False
	if can:
		print(biggest)
	else:
		print(-1)


import math
t = int(input())
for i in range(t):
	le = int(input())
	l = [int(i) for i in input().split()]
	lo = 0
	hi = 10 ** 9
	for i in range(le):
		if i:
			if l[i - 1] < l[i]:
				hi = min(hi, int((l[i] + l[i - 1]) / 2))
			elif l[i - 1] > l[i]:
				lo = max(lo, math.ceil((l[i] + l[i - 1]) / 2))
	if lo > hi:
		print(-1)
	else:
		print(lo)


import math
N = int(input())
for i in range(N):
	n = int(input())
	l = list(map(int, input().split()))
	left = 0
	right = 10000000000000
	for i in range(1, len(l)):
		if l[i - 1] < l[i]:
			right = min(right, (l[i] + l[i - 1]) // 2)
		if l[i - 1] > l[i]:
			left = max(left, math.ceil((l[i] + l[i - 1]) / 2))
	if left <= right:
		print(left)
	else:
		print(-1)


import math

def exe():
	maxi = 10 ** 9
	mini = 0
	for i in range(n - 1):
		avg = (lst[i] + lst[i + 1]) / 2
		if lst[i] > lst[i + 1]:
			mini = max(math.ceil(avg), mini)
		elif lst[i] < lst[i + 1]:
			maxi = min(math.floor(avg), maxi)
	if maxi >= mini:
		return mini
	else:
		return -1
	return
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	print(exe())


def checker(arr):
	count = 0
	for i in range(1, len(arr)):
		if arr[i] < arr[i - 1]:
			count += 1
	return count

def helper(arr):
	import math
	xx = 0
	for i in range(len(arr) - 1):
		if arr[i] > arr[i + 1]:
			xx = max(xx, math.ceil((arr[i] + arr[i + 1]) / 2))
	res = list(map(lambda x: abs(x - xx), arr))
	if res == sorted(res):
		return xx
	return -1
for i in range(int(input())):
	n = int(input())
	print(helper(list(map(int, input().split()))))


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			x = max(x, math.ceil((a[i] + a[i + 1]) / 2))
	for i in range(n):
		a[i] = abs(a[i] - x)
	if a == sorted(a):
		print(x)
	else:
		print(-1)


import math
t = int(input())
for i in range(t):
	_ = input()
	a = list(map(int, input().split()))
	minInt = 0
	maxInt = 10 ** 9
	for j in range(len(a) - 1):
		if a[j] < a[j + 1]:
			maxInt = min(math.floor((a[j] + a[j + 1]) / 2), maxInt)
		elif a[j] > a[j + 1]:
			minInt = max(math.ceil((a[j] + a[j + 1]) / 2), minInt)
	if minInt > maxInt:
		print(-1)
	else:
		print(minInt)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	lb = -1
	ub = 0
	for i in range(n - 1):
		mid = (l[i] + l[i + 1]) // 2
		if l[i + 1] < l[i]:
			if (l[i] + l[i + 1]) % 2 == 0:
				lb1 = (l[i] + l[i + 1]) // 2
			else:
				lb1 = (l[i] + l[i + 1]) // 2 + 1
			if lb1 > lb:
				lb = lb1
		elif l[i + 1] > l[i]:
			ub1 = mid
			if ub == 0 or ub1 < ub:
				ub = ub1
	if ub != 0 and ub < lb:
		print(-1)
	elif lb == -1:
		print(lb + 1)
	else:
		print(lb)


from math import ceil
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	x = 0
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			x = max(x, ceil((a[i] + a[i + 1]) / 2))
	for i in range(n - 1):
		if abs(a[i] - x) > abs(a[i + 1] - x):
			print(-1)
			break
	else:
		print(x)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mn = 0
	mx = int(1000000000.0)
	i = 0
	while i + 1 < n:
		x = a[i]
		y = a[i + 1]
		midL = (x + y) // 2
		midR = (x + y + 1) // 2
		if x < y:
			mx = min(mx, midL)
		if x > y:
			mn = max(mn, midR)
		i += 1
	if mn <= mx:
		print(mn)
	else:
		print(-1)


import math
n = int(input())
for i in range(n):
	k = int(input())
	lst = [int(x) for x in input().split()]
	c = 0
	for j in range(1, k):
		if abs(lst[j - 1] - c) > abs(lst[j] - c):
			c = math.ceil((lst[j - 1] + lst[j]) / 2)
	t = True
	for j in range(1, k):
		if abs(lst[j - 1] - c) > abs(lst[j] - c):
			print(-1)
			t = False
			break
	if t:
		print(int(c))


for _ in range(int(input())):
	len1 = int(input())
	x = 0
	list1 = list(map(int, input().split()))
	for i in range(1, len1):
		if list1[i] < list1[i - 1]:
			x = max(x, int((list1[i - 1] + list1[i] + 1) / 2))
	for i in range(len1):
		list1[i] = abs(list1[i] - x)
	flag = False
	for i in range(1, len1):
		if list1[i] < list1[i - 1]:
			flag = True
			break
	if flag:
		print(-1)
	else:
		print(x)


def ceil(x):
	return int(x // 1 + 1 if x > x // 1 else x // 1)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(mn, mx) = (0, 1000000000)
	for i in range(1, n):
		if arr[i - 1] < arr[i]:
			temp = (arr[i - 1] + arr[i]) // 2
			mx = min(mx, temp)
		elif arr[i - 1] > arr[i]:
			temp = ceil((arr[i - 1] + arr[i]) / 2)
			mn = max(mn, temp)
	print(mn) if mn <= mx else print(-1)


import math
for _ in range(int(input())):
	x = 0
	n = int(input())
	arr = list(map(int, input().split(' ')))
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			x = max(x, math.ceil((arr[i] + arr[i + 1]) / 2))
	for j in range(n):
		arr[j] = abs(arr[j] - x)
	for k in range(n - 1):
		if arr[k] > arr[k + 1]:
			x = -1
	print(x)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	(mm, mx) = (0, float('inf'))
	for i in range(n - 1):
		av = (lst[i] + lst[i + 1]) // 2
		av2 = (lst[i] + lst[i + 1] + 1) // 2
		if lst[i] < lst[i + 1]:
			mx = min(mx, av)
		if lst[i] > lst[i + 1]:
			mm = max(mm, av2)
	if mm <= mx:
		print(mm)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(mn, mx) = (0, int(1000000000.0))
	for i in range(n - 1):
		l = (a[i] + a[i + 1]) // 2
		r = (a[i] + a[i + 1] + 1) // 2
		if a[i] < a[i + 1]:
			mx = min(mx, l)
		if a[i] > a[i + 1]:
			mn = max(mn, r)
	print(mn if mn <= mx else '-1')