Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Jem couldn't even finish half of the homework exercises in "Advanced topics in algorithm" class. The teacher is really upset and gives him one final problem to solve - if he can't solve it, he is gonna fail the course.

Jem is given an array A consisting of N integers. The teacher asks him to remove exactly one number in the array to make the array become an arithmetic progressions.

Jem wanted to ask the teacher about the definition of arithmetic progressions but he remembered that he had heard this term in last week's lesson just before falling asleep. Now his life is in your hands again!

Anyways, we provide you the definition of arithmetic progression. Arithmetic progression is a sequence of numbers, where the difference between any two adjacent numbers is same.

------ Input ------ 

Input contains mutilpe test cases. The first line of the input contains a single integer T represents the number of tests. It is followed by T group of line represent the test cases.
Each test case consists of two lines where the first line contains a single integer N.
The second line contains N space separated integers denoting the array A.

------ Output ------ 

For each test case print out single integer which is the number you will remove from the array. If there is more than one solution take the smallest one. If there is no solution print out -1.

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

$1 ≤ T ≤ 10 $
$2 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
3
2
3 4
4
1 5 3 4
6
2 4 6 7 8 10
----- Sample Output 1 ------ 
3
-1
7
----- explanation 1 ------ 

test 1: an array contain a single integer is considered to be an arithmetic progression so you can remove any number in the array. But note that we must print out the smallest result which is 3.

test 2: there is no solution since none of [1, 3, 4], [1, 5, 3], [1, 5, 4], [5, 3, 4] is an arithmetic progressions.

test 3: the only way to archive an airthmetic progressions is remove the number 7 which will give us [2, 4, 6, 8, 10].

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	differences = defaultdict(lambda : 0)
	for i in range(1, N):
		differences[A[i] - A[i - 1]] += 1
	if len(differences) > 3:
		print(-1)
		continue
	ans = float('inf')
	for i in range(N):
		temp = differences.copy()
		if i > 0:
			temp[A[i] - A[i - 1]] -= 1
			if temp[A[i] - A[i - 1]] == 0:
				del temp[A[i] - A[i - 1]]
		if i < N - 1:
			temp[A[i + 1] - A[i]] -= 1
			if temp[A[i + 1] - A[i]] == 0:
				del temp[A[i + 1] - A[i]]
		if i != N - 1 and i != 0:
			temp[A[i + 1] - A[i - 1]] += 1
		if len(temp) <= 1:
			ans = min(ans, A[i])
	if ans != float('inf'):
		print(ans)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	f = [0] * n
	g = [0] * n
	if n <= 3:
		print(min(a))
	else:
		f[0] = f[1] = f[2] = 1
		for i in range(2, n):
			f[i] = a[i] - a[i - 1] == a[i - 1] - a[i - 2] and f[i - 1]
		g[n - 1] = g[n - 2] = 1
		for i in range(n - 3, -1, -1):
			g[i] = a[i + 1] - a[i] == a[i + 2] - a[i + 1] and g[i + 1]
		res = 10 ** 10
		if g[1]:
			res = min(res, a[0])
		if g[2]:
			if a[2] - a[0] == a[3] - a[2]:
				res = min(res, a[1])
		if f[n - 2]:
			res = min(res, a[n - 1])
		if f[n - 3]:
			if a[n - 3] - a[n - 1] == a[n - 4] - a[n - 3]:
				res = min(res, a[n - 2])
		for i in range(2, n - 2, 1):
			if f[i - 1] and g[i + 1] and (a[i + 1] - a[i - 1] == a[i + 2] - a[i + 1] == a[i - 1] - a[i - 2]):
				res = min(res, a[i])
		if res == 10 ** 10:
			print(-1)
		else:
			print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 2:
		print(min(a))
	elif n >= 3:
		l = []
		(d1, d2, d3) = (a[2] - a[0], a[2] - a[1], a[1] - a[0])
		for i in [d1, d3]:
			(x, y, count) = (a[0], 1, 0)
			while y < n:
				if a[y] - x != i:
					count += 1
					res = a[y]
				else:
					x = a[y]
				y += 1
				if count >= 2:
					break
			if count == 1:
				l.append(res)
			elif count == 0:
				l.append(min(a[0], a[-1]))
		(x, y, count) = (a[1], 2, 0)
		while y < n:
			if a[y] - x != d2:
				count += 1
				break
			x = a[y]
			y += 1
		if count == 0:
			l.append(a[0])
		if len(l) == 0:
			print(-1)
		else:
			print(min(l))


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	pre = [0] * n
	suff = [0] * n
	if n <= 3:
		print(min(l))
	else:
		pre[0] = pre[1] = pre[2] = 1
		for i in range(2, n):
			pre[i] = l[i] - l[i - 1] == l[i - 1] - l[i - 2] and pre[i - 1]
		suff[n - 1] = suff[n - 2] = 1
		for i in range(n - 3, -1, -1):
			suff[i] = l[i + 1] - l[i] == l[i + 2] - l[i + 1] and suff[i + 1]
		mini = 10 ** 10
		if suff[1]:
			mini = min(mini, l[0])
		if suff[2]:
			if l[2] - l[0] == l[3] - l[2]:
				mini = min(mini, l[1])
		if pre[n - 2]:
			mini = min(mini, l[n - 1])
		if pre[n - 3]:
			if l[n - 3] - l[n - 1] == l[n - 4] - l[n - 3]:
				mini = min(mini, l[n - 2])
		for i in range(2, n - 2, 1):
			if pre[i - 1] and suff[i + 1] and (l[i + 1] - l[i - 1] == l[i + 2] - l[i + 1] == l[i - 1] - l[i - 2]):
				mini = min(mini, l[i])
		if mini == 10 ** 10:
			print(-1)
		else:
			print(mini)


for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	if n <= 3:
		print(min(s))
	else:
		diff = list()
		s1 = dict()
		found = False
		prev = 0
		for j in range(n - 1):
			d = s[j + 1] - s[j]
			diff.append(d)
			if d not in s1:
				s1[d] = 1
			else:
				s1[d] += 1
			if j != 0 and (not found):
				if prev != d:
					a = j
					found = True
			prev = d
		if len(s1) > 3:
			print(-1)
			continue
		if len(s1) == 1:
			print(min(s))
			continue
		tp = False
		count = 0
		for key in s1:
			if s1[key] == 2:
				count += 1
				tp = True
			if s1[key] < 2:
				tp = False
				break
		if len(s1) == 3 or (len(s1) == 2 and tp):
			d1 = max(s1, key=s1.get)
			if s1[d1] != 1:
				for k in range(len(diff) - 1):
					if diff[k] + diff[k + 1] == d1:
						p_val = s[k + 1]
						break
				else:
					p_val = -1
			elif diff[0] + diff[1] == diff[2]:
				p_val = s[1]
			elif diff[1] + diff[2] == diff[0]:
				p_val = s[2]
			else:
				p_val = -1
			if len(s1) == 2 and count == 2 and (p_val == -1):
				del s1[d1]
				d1 = max(s1, key=s1.get)
				if s1[d1] != 1:
					for k in range(len(diff) - 1):
						if diff[k] + diff[k + 1] == d1:
							p_val = s[k + 1]
							break
					else:
						p_val = -1
				elif diff[0] + diff[1] == diff[2]:
					p_val = s[1]
				elif diff[1] + diff[2] == diff[0]:
					p_val = s[2]
				else:
					p_val = -1
			print(p_val)
			continue
		else:
			first = True
			last = True
			for k in range(len(diff)):
				if k != 0 and k != len(diff) - 1 and (diff[k] != diff[k + 1]):
					first = False
				if k != 0 and k != len(diff) - 1 and (diff[k] != diff[k - 1]):
					last = False
			if first:
				print(s[0])
			elif last:
				print(s[n - 1])
			else:
				print(-1)


T = int(input())
for t in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	if n < 4:
		print(min(a))
	elif n == 4:
		lst = []
		if a[2] - a[1] == a[3] - a[2]:
			lst.append(a[0])
		if a[2] - a[0] == a[3] - a[2]:
			lst.append(a[1])
		if a[1] - a[0] == a[3] - a[1]:
			lst.append(a[2])
		if a[1] - a[0] == a[2] - a[1]:
			lst.append(a[3])
		if lst:
			print(min(lst))
		else:
			print(-1)
	else:
		r = list(map(lambda x, y: x - y, a[1:], a))
		d = {}
		for rr in r:
			if rr in d:
				d[rr] += 1
			else:
				d[rr] = 1
		if len(d) == 1:
			print(min(a))
		else:
			v = max(d.keys(), key=lambda k: d[k])
			if n - d[v] == 2:
				if r[0] != v:
					print(a[0])
				elif r[-1] != v:
					print(a[-1])
				else:
					print(-1)
			elif n - d[v] == 3:
				notfound = True
				for i in range(1, n - 1):
					if r[i - 1] + r[i] == v:
						print(a[i])
						notfound = False
						break
				if notfound:
					print(-1)
			else:
				print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	if n == 2 or n == 3:
		print(min(arr))
		continue
	d = []
	for i in range(n - 1):
		d.append(arr[i + 1] - arr[i])
	cnt = {}
	for i in d:
		cnt[i] = cnt.get(i, 0) + 1
	maxele = -1
	maxi = -1
	for i in d:
		if cnt[i] > maxele:
			maxi = i
			maxele = cnt[i]
	index = -1
	chk = 1
	xk = 0
	for i in range(n - 1):
		if d[i] != maxi:
			chk = -1
			if i != 0 and i != n - 2:
				index = i + 1
			else:
				xk = 1
				if d[0] != maxi and d[1] != maxi:
					index = 1
				elif d[n - 2] != maxi and d[n - 3] != maxi:
					index = n - 2
				elif i == 0:
					index = i
				else:
					index = i + 1
			break
	if xk == 1:
		rem = arr.pop(index)
		d = []
		for i in range(n - 2):
			d.append(arr[i + 1] - arr[i])
		kk = 1
		for i in d:
			if i != d[0]:
				kk = -1
				break
		if kk == -1:
			print(-1)
		else:
			print(rem)
		continue
	if chk == 1:
		print(min(arr))
		continue
	chk = 1
	if arr[index + 1] - arr[index - 1] != maxi:
		print(-1)
		continue
	for i in range(index + 1, n - 1):
		if d[i] != maxi:
			chk = -1
			break
	if chk == -1:
		print(-1)
		continue
	else:
		print(arr[index])


t = int(input())
for sdasd in range(t):
	n = int(input())
	L = [int(x) for x in input().split()]
	d = {}
	for i in range(n - 1):
		diff = L[i + 1] - L[i]
		if diff not in d:
			d[diff] = 0
		d[diff] += 1
	if len(d) > 3:
		print(-1)
		continue
	possib = []
	for i in range(1, n - 1):
		d1 = L[i] - L[i - 1]
		d2 = L[i + 1] - L[i]
		d3 = L[i + 1] - L[i - 1]
		if d3 not in d:
			d[d3] = 0
		d[d1] -= 1
		d[d2] -= 1
		d[d3] += 1
		if len([x for x in d.values() if x > 0]) <= 1:
			possib.append(L[i])
		d[d1] += 1
		d[d2] += 1
		d[d3] -= 1
	if True:
		d1 = L[1] - L[0]
		d[d1] -= 1
		if len([x for x in d.values() if x > 0]) <= 1:
			possib.append(L[0])
		d[d1] += 1
		d1 = L[-1] - L[-2]
		d[d1] -= 1
		if len([x for x in d.values() if x > 0]) <= 1:
			possib.append(L[-1])
		d[d1] += 1
	if len(possib) > 0:
		print(min(possib))
	else:
		print(-1)