Mainak has an array $a_1, a_2, \ldots, a_n$ of $n$ positive integers. He will do the following operation to this array exactly once:

Pick a subsegment of this array and cyclically rotate it by any amount.

Formally, he can do the following exactly once:

Pick two integers $l$ and $r$, such that $1 \le l \le r \le n$, and any positive integer $k$.

Repeat this $k$ times: set $a_l=a_{l+1}, a_{l+1}=a_{l+2}, \ldots, a_{r-1}=a_r, a_r=a_l$ (all changes happen at the same time).

Mainak wants to maximize the value of $(a_n - a_1)$ after exactly one such operation. Determine the maximum value of $(a_n - a_1)$ that he can obtain.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 50$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 999$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.


-----Output-----

For each test case, output a single integer — the maximum value of $(a_n - a_1)$ that Mainak can obtain by doing the operation exactly once.


-----Examples-----

Input
5
6
1 3 9 11 5 7
1
20
3
9 99 999
4
2 1 8 1
3
2 1 5
Output
10
0
990
7
4


-----Note-----

In the first test case, we can rotate the subarray from index $3$ to index $6$ by an amount of $2$ (i.e. choose $l = 3$, $r = 6$ and $k = 2$) to get the optimal array: $$[1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}]$$ So the answer is $a_n - a_1 = 11 - 1 = 10$.

In the second testcase, it is optimal to rotate the subarray starting and ending at index $1$ and rotating it by an amount of $2$.

In the fourth testcase, it is optimal to rotate the subarray starting from index $1$ to index $4$ and rotating it by an amount of $3$. So the answer is $8 - 1 = 7$.

Difficulty: EASY
Tags: Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
for j in range(t):
	res = 0
	n = int(input())
	v = [0] * n
	arr = input().split()
	for i in range(n):
		v[i] = int(arr[i])
	for i in range(1, n):
		res = max(res, v[i] - v[0])
	for i in range(n - 1):
		res = max(res, v[n - 1] - v[i])
	for i in range(n - 1):
		res = max(res, v[i] - v[i + 1])
	print(res)


k = int(input())
for l in range(k):
	n = int(input())
	arr = list(map(int, input().split()))
	aa = 0
	if n > 1:
		a = arr.index(max(arr))
		b = arr.index(min(arr))
		if a == n - 1 or b == 0:
			print(max(arr) - min(arr))
		else:
			count1 = arr[n - 1] - arr[0]
			c = max(arr) - arr[0]
			d = arr[n - 1] - min(arr)
			count = max(c, d, count1)
			for i in range(n - 1):
				temp = arr[i] - arr[i + 1]
				if count < temp:
					count = temp
			print(count)
	else:
		print(0)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	if n == 1:
		print(0)
		continue
	temp1 = a[-1] - a[0]
	temp2 = a[0] - a[1]
	for i in range(1, n - 1):
		if a[i] - a[i + 1] > temp2:
			temp2 = a[i] - a[i + 1]
	temp3 = a[-1] - a[0]
	for i in range(1, n - 1):
		if a[-1] - a[i] > temp3:
			temp3 = a[-1] - a[i]
	temp4 = a[1] - a[0]
	for i in range(2, n):
		if a[i] - a[0] > temp4:
			temp4 = a[i] - a[0]
	print(max([temp1, temp2, temp3, temp4]))


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(k) for k in input().split(' ')]
	c = max(l[-1] - min(l), max(l) - l[0])
	for a in range(n):
		c = max(c, l[a - 1] - l[a])
	print(c)


for S in [*open(0)][2::2]:
	r = (*map(int, S.split()),)
	print(max(max(r) - r[0], r[-1] - min(r), *(b - a for (a, b) in zip(r, r[-1:] + r))))


def myMaxInx(a):
	m = a[0]
	inx = 0
	for i in range(len(a)):
		if a[i] > m:
			m = a[i]
			inx = i
	return inx

def myMinInx(a):
	m = a[0]
	inx = 0
	for i in range(len(a)):
		if a[i] < m:
			m = a[i]
			inx = i
	return inx

def myMaxDif(a):
	res = a[-1] - a[0]
	for i in range(1, len(a)):
		if res < a[i - 1] - a[i]:
			res = a[i - 1] - a[i]
	return res
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n > 2:
		maxInx = myMaxInx(a[1:-1]) + 1
		minInx = myMinInx(a[1:-1]) + 1
		cases = []
		cases.append(myMaxDif(a))
		cases.append(a[-1] - a[0])
		cases.append(a[0] - a[1])
		cases.append(a[maxInx] - a[0])
		cases.append(a[-1] - a[minInx])
		res = max(cases)
	elif n == 2:
		cases = []
		cases.append(a[1] - a[0])
		cases.append(a[0] - a[1])
		res = max(cases)
	else:
		res = 0
	print(res)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(0, n):
		ans = max(ans, arr[i] - arr[0])
		ans = max(ans, arr[n - 1] - arr[i])
		ans = max(ans, arr[i] - arr[(i + 1) % n])
	print(ans)
	ans = 0
	t = t - 1


tests = int(input())
for _ in range(tests):
	n = int(input())
	a = list(map(int, input().split()))
	ans = a[n - 1] - a[0]
	for i in range(n - 1):
		ans = max(ans, a[i] - a[i + 1])
	for i in range(n):
		ans = max(ans, a[i] - a[0])
	for i in range(n):
		ans = max(ans, a[n - 1] - a[i])
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(max(a) - a[0], a[-1] - min(a))
	for i in range(n - 1):
		m = max(m, a[i] - a[i + 1])
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	m = a[n - 1] - a[0]
	m = max(m, a[-1] - min(a[:-1]))
	m = max(m, max(a[0:]) - a[0])
	for i in range(n - 1):
		m = max(m, a[i] - a[i + 1])
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(j) for j in input().split()]
	if n == 1:
		print(0)
		continue
	one = max(arr[1:]) - arr[0]
	teo = arr[-1] - min(arr[:n - 1])
	three = -1 << 30
	for i in range(n):
		three = max(three, arr[i] - arr[(i + 1) % n])
	print(max(one, teo, three))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(0)
	elif n == 2:
		print(abs(arr[1] - arr[0]))
	else:
		ans = max(max(arr[1:]) - arr[0], arr[-1] - min(arr[:-1]))
		for i in range(n):
			ans = max(ans, arr[(i + n - 1) % n] - arr[i])
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	res = max(max(arr) - arr[0], arr[-1] - min(arr))
	for i in range(n - 1):
		res = max(res, arr[i] - arr[i + 1])
	print(res)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		return 0
	ans = arr[-1] - arr[0]
	for i in range(1, n):
		ans = max(ans, arr[i - 1] - arr[i])
	(v1, v2) = (min(arr[:n - 1]), max(arr[1:]))
	return max(arr[-1] - v1, v2 - arr[0], ans)
for _ in range(int(input())):
	print(solve())


def main():
	n = int(input())
	items = [int(i) for i in input().split()]
	if n == 1:
		return 0
	mR = 0
	for i in range(n):
		mR = max(items[-1 + i] - items[0 + i], mR)
	return max(max(items[1:]) - items[0], items[-1] - min(items[:-1]), mR)
t = int(input())
for asdasdsa in range(t):
	print(main())


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	a = min(l)
	b = max(l)
	for i in range(1, n):
		ans = max(ans, l[i - 1] - l[i])
	ans = max(ans, b - l[0], l[-1] - a)
	print(ans)


def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	res = max(max(a) - a[0], a[-1] - min(a))
	for (i, v) in enumerate(a[1:]):
		res = max(res, a[i] - v)
	print(res)
	return
for _ in range(int(input())):
	solve()


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		t = max(l[1:]) - l[0]
		t = max(t, l[-1] - min(l[:n - 1]))
		t = max(t, l[-1] - l[0])
		for i in range(n - 1):
			t = max(t, l[i] - l[i + 1])
		print(t)


def cal(n, arr):
	if n == 1:
		return 0
	ans = arr[-1] - arr[0]
	for i in range(n - 1):
		ans = max(ans, arr[i] - arr[i + 1])
	ans = max(ans, max(arr[1:]) - arr[0], arr[-1] - min(arr[:n - 1]))
	return ans
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(cal(n, arr))


def get_max_val():
	input()
	nums = list(map(int, input().strip().split()))
	max_val = nums[-1] - nums[0]
	if len(nums) == 1:
		return max_val
	max_val = max(max_val, max(nums[1:]) - nums[0])
	max_val = max(max_val, nums[-1] - min(nums[:-1]))
	for (l, r) in zip(nums, nums[1:]):
		max_val = max(max_val, l - r)
	return max_val
t = int(input())
for _ in range(t):
	print(get_max_val())


for _ in range(int(input())):
	n = int(input())
	if 'ijgt4j48gjtgn48j8' == 34343443434:
		print('Tanmay')
	a = [int(x) for x in input().split()]
	ans = a[-1] - a[0]
	for i in range(n - 1):
		ans = max(ans, a[i] - a[i + 1])
	ans = max(max(a) - a[0], ans, a[-1] - min(a))
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ma = 0
	for j in range(1, n):
		ma = max(ma, l[j] - l[0])
	for j in range(0, n - 1):
		ma = max(ma, l[n - 1] - l[j])
	for j in range(n - 1):
		ma = max(ma, l[j] - l[j + 1])
	print(ma)


for caseno in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	answers = []
	(i, j) = (0, n - 1)
	(max_ele, min_ele) = (l[0], l[0])
	diff_answer = l[n - 1] - l[0]
	while i < n:
		(max_ele, min_ele) = (max(max_ele, l[i]), min(min_ele, l[i]))
		curr_diff = l[j % n] - l[i]
		diff_answer = max(diff_answer, curr_diff)
		i += 1
		j += 1
	answers += [diff_answer]
	answers += [max_ele - l[0]]
	answers += [l[n - 1] - min_ele]
	answer = max(answers)
	print(answer)


t = int(input())
for o in range(0, t):
	n = int(input())
	a = input().split()
	if n == 1:
		print(0)
	else:
		for i in range(0, n):
			a[i] = int(a[i])
		maxi = a[n - 1] - a[0]
		for i in range(1, n):
			maxi = max(a[i - 1] - a[i], maxi)
			maxi = max(a[i] - a[0], maxi)
			maxi = max(a[n - 1] - a[i - 1], maxi)
		print(maxi)


import sys
input = sys.stdin.readline
tests = int(input())
for test in range(tests):
	n = int(input())
	a = list(map(int, input().split()))
	adj = [0]
	for item in range(len(a) - 1):
		adj.append(a[item] - a[item + 1])
	print(max(max(a) - a[0], a[-1] - min(a), max(adj)))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		answer = max(max(a[1:]) - a[0], a[-1] - min(a[:-1]), max([a[i] - a[i + 1] for i in range(len(a) - 1)]))
		print(answer)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = a[n - 1] - a[0]
	ma = max(a)
	mi = min(a)
	for i in range(n - 1):
		ans = max(ans, a[i] - a[i + 1])
	ans = max(ans, ma - a[0])
	ans = max(ans, a[n - 1] - mi)
	print(ans)


import sys
from math import *
from bisect import *
mod_ = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 7)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	max_ = a[-1] - a[0]
	for i in range(1, n):
		max_ = max(max_, a[i - 1] - a[i])
	max_ = max(max(a[1:]) - a[0], max_)
	max_ = max(a[-1] - min(a[:-1]), max_)
	print(max_)


for _ in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	minn = y[0]
	maxx = y[0]
	maxx3 = 0
	for i in y:
		if i > maxx:
			maxx = i
		if i < minn:
			minn = i
	for i in range(x - 1):
		if y[i] - y[i + 1] > maxx3:
			maxx3 = y[i] - y[i + 1]
	maxx2 = 0
	if y.index(maxx) != x - 1:
		maxx2 = maxx - y[y.index(maxx) + 1]
	print(max(max(max(maxx - y[0], y[-1] - minn), maxx2), maxx3))


def solve():
	x = int(input())
	for __ in range(x):
		n = int(input())
		arr = list(map(int, input().split()))
		md = 0
		ma = arr[0]
		mi = arr[0]
		for i in range(len(arr)):
			md = max(md, arr[i - 1] - arr[i])
			ma = max(arr[i], ma)
			mi = min(arr[i], mi)
		print(max(ma - arr[0], arr[n - 1] - mi, md))
solve()


def sol(A):
	if len(A) == 1:
		return 0
	maxx = max(A)
	minn = min(A)
	ans = -2 ** 31
	for i in range(1, len(A)):
		ans = max(ans, A[i - 1] - A[i])
	return max(ans, maxx - A[0], A[-1] - minn)
x = int(input())
for _ in range(x):
	n = int(input())
	A = list(map(int, input().split()))
	print(sol(A))


length = int(input())
for _ in range(length):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	res = 0
	for i in range(n - 1):
		res = max(res, lst[i] - lst[i + 1])
	res = max(res, max(lst) - lst[0])
	res = max(res, lst[-1] - min(lst))
	print(res)


for Pythonic__Python in range(int(input())):
	n = int(input())
	ans = 0
	l = list(map(int, input().split()))
	for i in range(len(l) - 1):
		ans = max(ans, l[i] - l[i + 1])
	print(max(l[n - 1] - min(l), max(l) - l[0], ans))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	difs = [l[i] - l[(i + 1) % n] for i in range(n)]
	print(max(max(l) - l[0], l[n - 1] - min(l), max(difs)))


def get_ans(a):
	n = len(a)
	if n == 1:
		return 0
	m = a[-1] - a[0]
	for i in range(n - 1):
		m = max(m, a[i] - a[i + 1])
	m = max(m, max(a[1:]) - a[0])
	m = max(m, a[-1] - min(a[:-1]))
	return m
t = int(input())
for _ in range(t):
	input()
	print(get_ans([int(i) for i in input().split()]))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = [int(i) for i in input().split()]
	maxe = l[n - 1]
	mine = l[n - 1]
	m = l[n - 1] - l[0]
	for i in range(n - 1):
		if l[i] - l[i + 1] > m:
			m = l[i] - l[i + 1]
		if l[i] > maxe:
			maxe = l[i]
		if l[i] < mine:
			mine = l[i]
	if maxe - l[0] > m:
		m = maxe - l[0]
	if l[n - 1] - mine > m:
		m = l[n - 1] - mine
	print(m)


q = int(input())
for _ in range(q):
	n = int(input())
	m = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	mx = max([m[i] - m[(i + 1) % n] for i in range(n)])
	mx = max(mx, max(m[1:]) - m[0], m[n - 1] - min(m[:n - 1]))
	print(mx)


def solution():
	n = int(input())
	a = [int(num) for num in input().split()]
	if n == 1:
		print(0)
		return
	d1 = max(a[1:]) - a[0]
	d2 = a[n - 1] - min(a[:n - 1])
	ans = max(d1, d2)
	for i in range(1, n):
		ans = max(ans, a[i - 1] - a[i])
	print(ans)

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	a = lst[n - 1] - min(lst)
	b = max(lst) - lst[0]
	c = -1000000
	for i in range(n):
		c = max(lst[n - 1] - lst[0], c)
		x = lst[n - 1]
		lst.pop(n - 1)
		lst.insert(0, x)
	print(max(a, b, c))


in_il = lambda : list(map(int, input().split()))
in_sl = lambda : input().split()
in_i = lambda : int(input())
MAX_INT = float('inf')

def solve():
	n = in_i()
	arr = in_il()
	max_num = 0
	min_num = MAX_INT
	ans = -MAX_INT
	for i in range(n):
		max_num = max(max_num, arr[i])
		min_num = min(min_num, arr[i])
		ans = max(ans, arr[i] - arr[(i + 1) % n])
	print(max(ans, max_num - arr[0], arr[n - 1] - min_num))
for _ in range(in_i()):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	maxi_1 = 0
	for i in range(len(a)):
		j = i + 1
		if j >= len(a):
			j = 0
		if a[i] - a[j] > maxi_1:
			maxi_1 = a[i] - a[j]
	maxi_2 = a[n - 1] - min(a[0:n - 1] or a)
	maxi_3 = max(a[1:n] or a) - a[0]
	print(max(maxi_1, maxi_2, maxi_3))


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	maxEl = max(lst)
	minEl = min(lst)
	maxDiff = -float('inf')
	for i in range(n - 1):
		maxDiff = max(maxDiff, lst[i] - lst[i + 1])
	print(max([maxDiff, maxEl - lst[0], lst[n - 1] - minEl]))


for t in range(0, int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	max_ = 0
	for i in range(1, len(a)):
		if max_ < a[i] - a[0]:
			max_ = a[i] - a[0]
	for i in range(0, len(a) - 1):
		if max_ < a[len(a) - 1] - a[i]:
			max_ = a[len(a) - 1] - a[i]
	max2 = 0
	for i in range(0, len(a)):
		if max2 < a[i - 1] - a[i]:
			max2 = a[i - 1] - a[i]
	if max2 > max_:
		max_ = max2
	print(max_)


import sys
input = sys.stdin.readline

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

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

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

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	arr = inlt()
	if n == 1:
		print(0)
	else:
		mx_val = 0
		mx_dif = 0
		mn_val = 1000
		for i in range(n):
			mx_val = max(mx_val, arr[i])
			mn_val = min(mn_val, arr[i])
			mx_dif = max(mx_dif, max(arr[(i - 1) % n] - arr[i], arr[i] - arr[(i + 1) % n]))
		val = mx_val - arr[0]
		print(max(val, mx_dif, arr[-1] - mn_val))


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	max1 = 0
	(max, min) = (arr[0], arr[0])
	for j in range(1, n):
		if arr[j - 1] - arr[j] > max1:
			max1 = arr[j - 1] - arr[j]
		if arr[j] > max:
			max = arr[j]
		if arr[j] < min:
			min = arr[j]
	abs_max = max1
	if max - arr[0] > abs_max:
		abs_max = max - arr[0]
	if arr[n - 1] - min > abs_max:
		abs_max = arr[n - 1] - min
	print(abs_max)


import math

def solve():
	n = int(input())
	lst = list(map(int, input().split(' ')))
	mx = lst[-1] - lst[0]
	for i in range(n - 1):
		mx = max(mx, lst[i] - lst[i + 1])
	mx = max(mx, lst[-1] - min(lst))
	mx = max(mx, max(lst) - lst[0])
	print(mx)
t = int(input())
while t:
	t -= 1
	solve()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n > 1:
		maxi = max(l[1:])
		mini = min(l[:-1])
		vals = []
		for i in range(n):
			vals.append(l[i - 1] - l[i])
		vals.append(maxi - l[0])
		vals.append(l[-1] - mini)
		print(max(vals))
	else:
		print(0)


x = int(input())
for i in range(x):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		ans = []
		f = arr[0]
		l = arr[n - 1]
		ma = max(arr[1:])
		mi = min(arr[:n - 1])
		ans.append(ma - f)
		ans.append(l - mi)
		for j in range(n - 1):
			ans.append(arr[j] - arr[j + 1])
		print(max(ans))


n = int(input())
for p in range(0, n):
	m = int(input())
	a = list(map(int, input().split()))
	mm = a[0]
	mmm = a[m - 1]
	maxx = 0
	cc = 0
	if m != 1:
		for i in range(0, m - 1):
			cc = a[i] - a[i + 1]
			maxx = max(maxx, cc)
	a1 = max(a) - mm
	a2 = mmm - min(a)
	ans = max(a1, a2, maxx)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	ans = arr[-1] - arr[0]
	ans = max(ans, arr[-1] - min(arr[:-1]))
	ans = max(ans, max(arr[1:]) - arr[0])
	for i in range(n):
		ans = max(ans, arr[i] - arr[(i + 1) % n])
	print(ans)


import sys
input = sys.stdin.readline

def int_num():
	return int(input())

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

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

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

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

def solve():
	n = int_num()
	a = int_list()
	(max_a, min_a) = (max(a), min(a))
	ans = max(max_a - a[0], a[-1] - min_a)
	if n >= 2:
		max_2 = max([a[i] - a[i + 1] for i in range(n - 1)])
		ans = max(ans, max_2)
		ans = max(ans, a[-1] - a[0])
	print(ans)

def main():
	t = int_num()
	while t:
		solve()
		t -= 1
	return
main()


def fun(a):
	mn = min(a)
	mx = max(a)
	if len(a) == 1:
		return 0
	if a[-1] == mx or a[0] == mn:
		return mx - mn
	m = max(mx - a[0], a[-1] - mn)
	for i in range(len(a) - 1):
		m = max(m, a[i] - a[i + 1])
	return m
for _ in range(int(input())):
	x = int(input())
	a = list(map(int, input().split()))
	print(fun(a))


for h in range(int(input())):
	n = int(input())
	temp = list(map(int, input().split()))
	var = 0
	if n == 1:
		print(0)
		continue
	for i in range(n):
		var = max(var, temp[i] - temp[(i + 1) % n])
	print(max(temp[0] - temp[1], max(temp[1:]) - temp[0], temp[n - 1] - min(temp[:n - 1]), var))


for pratyush in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = 0
	for i in range(n - 1):
		f = max(f, a[i] - a[i + 1])
	for i in range(n - 1):
		f = max(f, a[n - 1] - a[i])
	for i in range(1, n):
		f = max(f, a[i] - a[0])
	print(f)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	for i in range(0, n):
		if a[i - 1] - a[i] > k:
			k = a[i - 1] - a[i]
	m1 = max(a) - a[0]
	m2 = a[-1] - min(a)
	print(max(m1, m2, k))


def max_array_diff(arr):
	if len(arr) < 2:
		return 0
	choice1 = arr[-1] - min(arr[:-1])
	choice2 = max(arr[0:]) - arr[0]
	choice3 = max([arr[i % len(arr)] - arr[(i + 1) % len(arr)] for i in range(len(arr))])
	return max(choice1, choice2, choice3)
num_tests = int(input())
for _ in range(num_tests):
	t = int(input())
	arr = list(map(int, input().split()))
	print(max_array_diff(arr))


t = int(input())
for testcase in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	maxi = max(arr)
	mini = min(arr)
	if arr[0] == mini or arr[n - 1] == maxi:
		print(maxi - mini)
	else:
		best = arr[n - 1] - arr[0]
		for i in range(n - 1):
			best = max(best, arr[i] - arr[i + 1], arr[n - 1] - arr[i], arr[i + 1] - arr[0])
		print(best)


t = int(input())
while t:
	p = int(input())
	s = list(map(int, input().split()))
	m = 0
	if p == 1:
		print(0)
	else:
		for i in range(p):
			m = max(m, s[i] - s[(i + 1) % p])
		check1 = min(s[:-1])
		check2 = max(s[1:])
		m = max(m, check2 - s[0])
		m = max(m, s[p - 1] - check1)
		print(m)
	t -= 1


import sys

def read():
	cases = int(sys.stdin.readline())
	for k in range(cases):
		_ = int(sys.stdin.readline())
		nums = [int(num) for num in sys.stdin.readline().split(' ')]
		print(solve(nums))

def solve(arr):
	best = float('-inf')
	for k in range(len(arr)):
		best = max(best, arr[len(arr) - k - 1] - arr[(len(arr) - k) % len(arr)])
	if len(arr) > 1:
		best = max(best, max(arr[1:]) - arr[0])
		best = max(best, arr[-1] - min(arr[:len(arr) - 1]))
	return best
read()


t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	(mi, ma) = (min(a), max(a))
	ans = 0
	for i in range(n - 1):
		ans = max(ans, a[i] - a[i + 1])
	for i in range(n - 1):
		ans = max(ans, a[n - 1] - a[i])
	for i in range(n):
		ans = max(ans, a[i] - a[0])
	print(ans)
	t -= 1


test = int(input())
for t in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	res = -float('inf')
	a = -float('inf')
	b = float('inf')
	for i in range(n):
		res = max(res, arr[i] - arr[(i + 1) % n])
	for i in range(n - 1):
		b = min(b, arr[i])
	for i in range(1, n):
		a = max(a, arr[i])
	res = max(res, a - arr[0])
	res = max(res, arr[n - 1] - b)
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	for i in range(n - 1):
		ans = max(ans, a[i] - a[i + 1], a[n - 1] - a[i], a[i] - a[0])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	n1 = n
	ans = 0
	if n == 1:
		print(0)
	else:
		for i in range(n - 1):
			ans = max(num[i] - num[i + 1], ans)
		for i in range(n - 1):
			ans = max(ans, num[n - 1] - num[i])
		for i in range(1, n):
			ans = max(num[i] - num[0], ans)
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		ans = 0
		for i in range(0, n - 1):
			ans = max(ans, lst[i] - lst[i + 1])
		for i in range(0, n - 1):
			ans = max(ans, lst[n - 1] - lst[i])
		for i in range(1, n):
			ans = max(ans, lst[i] - lst[0])
		print(ans)


def solve():
	n = int(input())
	z = list(map(int, input().split()))
	res = z[-1] - z[0]
	for i in range(n):
		res = max(res, z[i] - z[0], z[-1] - z[i])
		if i:
			res = max(res, z[i - 1] - z[i])
		if i < n - 1:
			res = max(res, z[i] - z[i + 1])
	print(res)
t = int(input())
for _ in range(t):
	solve()


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	maxx = max(l)
	minn = min(l)
	if l[0] != minn or l[n - 1] != maxx:
		l1 = []
		l1.append(max(l[1:]) - l[0])
		l1.append(l[n - 1] - min(l[:n - 1]))
		l1.append(l[n - 1] - l[0])
		for j in range(n - 1):
			l1.append(l[j] - l[j + 1])
		print(max(l1))
	else:
		print(maxx - minn)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if len(l) == 1:
		print(0)
	else:
		m = -10000
		if l[-1] - min(l[:-1]) > m:
			m = l[-1] - min(l[:-1])
		if max(l[1:]) - l[0] > m:
			m = max(l[1:]) - l[0]
		for i in range(0, len(l) - 1):
			if l[i] - l[i + 1] > m:
				m = l[i] - l[i + 1]
		if l[-1] - l[0] > m:
			m = l[-1] - l[0]
		print(m)


for _ in range(int(input())):
	m = int(input())
	lst = list(map(int, input().split()))
	max_ = 0
	for i in range(m):
		if i == 0:
			val = lst[-1] - lst[0]
		else:
			val = lst[i - 1] - lst[i]
		if val > max_:
			max_ = val
	for i in range(m):
		if lst[i] - lst[0] > max_:
			max_ = lst[i] - lst[0]
		if lst[-1] - lst[i] > max_:
			max_ = lst[-1] - lst[i]
	print(max_)


for ps in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = max(a) - a[0]
	c = a[-1] - min(a)
	s = []
	for i in range(n - 1):
		s.append(a[i] - a[i + 1])
	if n == 1:
		print(0)
		continue
	else:
		print(max(b, c, max(s)))


for i in range(int(input())):
	b = 0
	a = []
	pp = int(input())
	max1 = 0
	min1 = 999999
	for j in map(int, input().split()):
		a.append(j)
	for j in range(1, pp):
		if a[j - 1] - a[j] > b:
			b = a[j - 1] - a[j]
	if a[-1] - a[0] > b:
		b = a[-1] - a[0]
	for j in range(1, pp - 1):
		if max1 < a[j]:
			max1 = a[j]
		if min1 > a[j]:
			min1 = a[j]
	if b < max1 - a[0]:
		b = max1 - a[0]
	if b < a[-1] - min1:
		b = a[-1] - min1
	print(b)


from re import I, L
import sys
printf = sys.stdout.write

def intput():
	return int(sys.stdin.readline())

def get_int():
	return map(int, sys.stdin.readline().strip().split())

def get_lis():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_liss():
	return sys.stdin.readline().split()

def get_ints():
	return sys.stdin.readline().split()

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

def pop_zeros(items):
	while items[-1] == 0:
		items.pop()

def compute_lcm(x, y):
	if x > y:
		greater = x
	else:
		greater = y
	while True:
		if greater % x == 0 and greater % y == 0:
			lcm = greater
			break
		greater += 1
	return lcm
from collections import defaultdict
import math
t = intput()
for p in range(t):
	n = intput()
	l = get_lis()
	ll = l.copy()
	ans = []
	m = max(l)
	mm = min(l)
	ans.append(m - l[0])
	ans.append(l[-1] - mm)
	for i in range(n - 1):
		ans.append(l[i] - l[i + 1])
	ans.append(l[-1] - l[0])
	printf(str(max(ans)))
	printf('\n')


t = int(input())
for t1 in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if len(l) == 1:
		print(0)
	else:
		ans = max(-l[0] + max(l[1:]), l[len(l) - 1] - min(l[0:len(l) - 1]))
		ans = max(ans, l[len(l) - 1] - l[0])
		for (x, y) in zip(l, l[1:]):
			ans = max(ans, x - y)
		print(ans)


t = eval(input())
for _ in range(t):
	n = eval(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	k1 = min(a)
	k2 = max(a)
	d = []
	d.append(k2 - a[0])
	d.append(a[1] - a[0])
	d.append(a[-1] - k1)
	d.append(a[-2] - a[-1])
	for i in range(1, n - 1):
		d.append(a[-1] - a[i])
		d.append(a[i - 1] - a[i])
		d.append(a[i] - a[0])
		d.append(a[i] - a[i + 1])
	print(max(d))


for _ in range(int(input())):
	poss_ans = []
	input()
	array = list(map(int, input().split()))
	if len(array) == 1:
		print(0)
		continue
	poss_ans.append(array[-1] - min(array[:-1]))
	poss_ans.append(max(array[1:]) - array[0])
	nums = []
	for i in range(len(array) - 1):
		nums.append(array[i] - array[i + 1])
	poss_ans.append(max(nums))
	print(max(poss_ans))


n = int(input())
for i in range(n):
	m = int(input())
	v = list(map(int, input().split()))
	v1 = []
	for j in range(m - 1):
		v1.append(v[j] - v[j + 1])
	v1.append(v[m - 1] - v[0])
	z = max(v1)
	x = max(v)
	y = min(v)
	if x == v[0]:
		if len(v) != 1:
			t = v[1]
		else:
			t = v[0]
	else:
		t = v[0]
	t = x - t
	if y == v[m - 1]:
		if len(v) != 1:
			r = v[m - 2]
		else:
			r = v[m - 1]
	else:
		r = v[m - 1]
	r = r - y
	r = max(r, t)
	print(max(r, z))


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	lm = 1000
	rm = 0
	mm = 0
	for i in range(n):
		if l[i - 1] - l[i] > mm:
			mm = l[i - 1] - l[i]
	for i in range(n - 1):
		if l[i] < lm:
			lm = l[i]
	lm = l[-1] - lm
	for i in range(1, n):
		if l[i] > rm:
			rm = l[i]
	rm = rm - l[0]
	a = []
	a.append(mm)
	a.append(rm)
	a.append(lm)
	a.sort()
	print(int(math.fabs(a[-1])))


times = int(input())
for time in range(times):
	n = int(input())
	arr = [int(x) for x in input().split()]
	mn = min(arr)
	mx = max(arr)
	if mx - arr[0] < arr[-1] - mn:
		value = arr[-1] - mn
	else:
		value = mx - arr[0]
	for i in range(n - 1):
		if arr[i] - arr[i + 1] > value:
			value = arr[i] - arr[i + 1]
	print(value)


n = int(input())
for _ in range(n):
	length = int(input())
	nums = input().split(' ')
	nums = list(map(int, nums))
	maxvalue = max(nums)
	minvalue = min(nums)
	flag = False
	maxtemp = 0
	for i in range(length - 1):
		maxtemp = max(maxtemp, nums[i] - nums[i + 1])
		if nums[i] == maxvalue and nums[i + 1] == minvalue:
			flag = True
	if nums[0] == minvalue or nums[length - 1] == maxvalue or flag:
		print(maxvalue - minvalue)
	else:
		print(max(max(nums[1:]) - nums[0], nums[length - 1] - min(nums[:length - 1]), maxtemp))


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


t = int(input())
for i in range(t):
	n = int(input())
	s = [int(x) for x in input().split()]
	t = max(max(s) - s[0], s[n - 1] - min(s))
	for i in range(n - 1):
		if s[i] - s[i + 1] > t:
			t = s[i] - s[i + 1]
		elif s[-1] - s[0] > t:
			t = s[-1] - s[0]
		else:
			continue
	print(t)


ad = int(input())
for i in range(ad):
	n = int(input())
	a = list(map(int, input().split()))
	res = 0
	for i in range(1, n):
		res = max(res, a[i] - a[0])
	for i in range(0, n - 1):
		res = max(res, a[i] - a[i + 1])
	for i in range(n - 1, -1, -1):
		res = max(res, a[n - 1] - a[i])
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(v) for v in input().split()]
	(f, l, p) = (a[0], a[-1], a[0])
	m_dif = l - f
	for (i, ai) in enumerate(a):
		if i == 0:
			continue
		if p - ai > m_dif:
			m_dif = p - ai
		if ai - f > m_dif:
			m_dif = ai - f
		if l - ai > m_dif:
			m_dif = l - ai
		p = ai
	print(m_dif)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ma = max(arr)
	mi = min(arr)
	ck = -100000
	if n == 1:
		print(0)
	else:
		for i in range(0, n - 1):
			if arr[i] - arr[i + 1] > ck:
				ck = arr[i] - arr[i + 1]
		print(max(ck, max(ma - arr[0], arr[-1] - mi)))


for b in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	mi = ar[0]
	ma = ar[n - 1]
	con = 0
	for a in range(1, n - 1):
		mi = min(mi, ar[a])
		ma = max(ma, ar[a])
		if con < ar[a - 1] - ar[a]:
			con = ar[a - 1] - ar[a]
	if con < ar[n - 2] - ar[n - 1]:
		con = ar[n - 2] - ar[n - 1]
	print(max(ar[n - 1] - mi, ma - ar[0], con))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	minA = float('inf')
	maxA = 0
	for i in range(n):
		if i == 0:
			minA = a[i]
			maxA = a[i]
		else:
			if a[i] > maxA:
				maxA = a[i]
			if minA > a[i]:
				minA = a[i]
	output = 0
	for i in range(n):
		if i != n - 1:
			output = max(output, a[i] - a[i + 1])
	output = max(output, a[n - 1] - a[0])
	output = max(output, a[n - 1] - minA)
	output = max(output, maxA - a[0])
	print(output)


def func(arr, n):
	if len(arr) <= 1:
		return 0
	(ma, mi) = (arr[0], arr[0])
	(ma_loc, mi_loc) = (0, 0)
	diff = 0
	for i in range(1, n):
		diff = max(diff, arr[i - 1] - arr[i])
		if arr[i] < mi:
			mi = arr[i]
			mi_loc = i
		elif arr[i] > ma:
			ma = arr[i]
			ma_loc = i
	if ma_loc == n - 1 or mi_loc == 0:
		return ma - mi
	return max(ma - arr[0], arr[n - 1] - mi, diff)
T = int(input())
for tc in range(T):
	n = int(input())
	arr = [int(a) for a in input().split(' ')]
	print(func(arr, n))


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	u = -1
	if n != 1:
		for j in range(0, len(a)):
			p = a[j] - a[(j + 1) % len(a)]
			u = max(u, p)
		q = max(a) - a[0]
		r = a[len(a) - 1] - min(a)
		u = max(u, q, r)
		print(u)
	else:
		print(0)


n = int(input())
l = []
for i in range(0, n):
	n1 = int(input())
	s = [int(x) for x in input().split()]
	l.append(s)
for x in range(0, n):
	m = min(l[x])
	M = max(l[x])
	if l[x][0] == m or l[x][-1] == M:
		print(M - m)
	else:
		s1 = M - l[x][0]
		s2 = l[x][-1] - m
		t = max(s1, s2)
		for y in range(0, len(l[x]) - 1):
			if l[x][y] - l[x][y + 1] > t:
				t = l[x][y] - l[x][y + 1]
			elif l[x][-1] - l[x][0] > t:
				t = l[x][-1] - l[x][0]
		print(t)


tt = int(input())
l = []
for i in range(0, tt):
	n = int(input())
	m = [int(x) for x in input().split()]
	l.append(m)
for j in range(0, tt):
	p = l[j]
	k1 = max(p)
	k2 = min(p)
	t = max(k1 - p[0], p[-1] - k2)
	for k in range(0, len(p) - 1):
		if p[k] - p[k + 1] > t:
			t = p[k] - p[k + 1]
		elif p[-1] - p[0] > t:
			t = p[-1] - p[0]
		else:
			continue
	print(t)


import math
for i in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	mn = min(a)
	mx = max(a)
	if a[0] == mn and a[n - 1] == mx:
		print(a[n - 1] - a[0])
	else:
		mot = 0
		sot = 0
		lot = math.inf
		for i in range(n - 1):
			mot = max(a[i] - a[i + 1], mot)
			lot = min(lot, a[i])
			sot = max(sot, a[i + 1])
		print(max(sot - a[0], a[n - 1] - lot, mot))


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	a = tuple(map(int, input().split()))
	ansd = False
	b_ind = []
	mx = max(a)
	mn = min(a)
	proans = []
	for i in range(n):
		proans.append(a[i - 1] - a[i])
		proans.append(a[-1] - a[i])
		proans.append(a[i] - a[0])
	ans.append(max(proans))
for i in ans:
	print(i)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		r = 0
		for i in range(n - 1):
			r = max(r, l[i] - l[i + 1])
		for j in range(n - 1):
			r = max(r, l[n - 1] - l[j])
		for k in range(1, n):
			r = max(r, l[k] - l[0])
		print(r)


def sol():
	g = int(input())
	arr = list(map(int, input().split(' ')))
	d = -293425930
	for i in range(len(arr)):
		d = max(d, -arr[(i + 1) % len(arr)] + arr[i])
	l = max(arr)
	s = min(arr)
	return max(l - arr[0], arr[g - 1] - s, d)
i = int(input())
while i != 0:
	i = i - 1
	print(sol())