Tired of the overpopulated world, Miu - The introverted cat visits a new continent in search for a new house.  
There are $N$ houses lying on the X-axis.

Their positions are given by $X$$i$ , where $i$ refers to the $i$th house. ( $1 <= i <= N$ )

Each of these positions are pairwise distinct 
Miu is supposed to choose one of these houses for herself.

Miu defines a term - The Distance of Peace,  as the minimum distance from her house to any other house.  
Miu wonders what is maximum Distance of Peace she can obtain. Can you help her?

-----Input:-----
- The first line of the input consists of a single integer $T$, denoting the number of test cases  
- The first line of each test case consists of a single integer $N$ 
- The second line of each test case consists of $N$ space-separated integers
$X$$1$ $X$$2$ $X$$3$ … $X$$N$

-----Output:-----
- For each test case print the answer in a single line, the maximum Distance of Peace Miu can obtain

-----Constraints-----
- 1 <= $T$ <= 100  
- 2 <= $N$ <= 105 
- -109 <= $X$$i$ <= 109 
- Sum of $N$ over all test cases does not exceed 106 

-----Subtasks-----
Subtask #1 (30 points): 
- $N$ <= 103 
Subtask #2 (70 points): 
- Original Constraints

-----Sample Input:-----
2

6

7 -1 2 13 -5 15

4

6 10 3 12  

-----Sample Output:-----
5

3  

-----EXPLANATION:-----
Test Case 1:

The $1$st house has the maximum Distance of Peace, which is from the $3$rd house:
$| 7 - 2 | = 5$

Hence, the answer is $5$

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
n = int(input())
for i in range(n):
	t = int(input())
	li = sorted(list(map(int, input().split())))
	ans = 1
	dp = [li[1] - li[0]] + [0] * (t - 2) + [li[t - 1] - li[t - 2]]
	for i in range(1, t - 1):
		dp[i] = min(li[i] - li[i - 1], li[i + 1] - li[i])
	print(max(dp))


n = int(input())
for i in range(n):
	p = int(input())
	l = list(map(int, input().split()))
	l.sort()
	minlist = []
	minlist.append(abs(l[0] - l[1]))
	minlist.append(abs(l[len(l) - 1] - l[len(l) - 2]))
	for i in range(1, len(l) - 1):
		r = abs(l[i] - l[i - 1])
		p = abs(l[i] - l[i + 1])
		minlist.append(min(r, p))
	print(max(minlist))


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	m = list()
	m.append(abs(l[0] - l[1]))
	m.append(abs(l[-1] - l[-2]))
	for i in range(1, n - 1, 1):
		if abs(l[i] - l[i - 1]) < abs(l[i] - l[i + 1]):
			m.append(abs(l[i] - l[i - 1]))
		else:
			m.append(abs(l[i] - l[i + 1]))
	print(max(m))
	t -= 1


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


def Testcase():
	n = int(input())
	li = list(map(int, input().split()))[:n]
	if n == 2:
		print(abs(li[1] - li[0]))
		return
	li.sort()
	ans = 0
	for i in range(1, n - 1):
		prev = abs(li[i] - li[i - 1])
		next = abs(li[i + 1] - li[i])
		curr = min(prev, next)
		ans = max(ans, curr)
	ans = max(ans, abs(li[1] - li[0]))
	ans = max(ans, abs(li[n - 1] - li[n - 2]))
	print(ans)
t = int(input())
for i in range(t):
	Testcase()


t = int(input())
for rep in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	x.sort()
	l = []
	if n > 2:
		for i in range(1, n - 1):
			l.append(min(x[i] - x[i - 1], x[i + 1] - x[i]))
		l.append(x[1] - x[0])
		l.append(x[n - 1] - x[n - 2])
	else:
		l.append(x[1] - x[0])
	print(max(l))


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	mv = max(A[1] - A[0], A[N - 1] - A[N - 2])
	for i in range(1, N - 1):
		a = min(A[i + 1] - A[i], A[i] - A[i - 1])
		mv = max(a, mv)
	print(mv)


for _ in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	maxi = float('-inf')
	for i in range(n):
		mini = float('inf')
		if i - 1 >= 0:
			mini = min(mini, abs(a[i] - a[i - 1]))
		if i + 1 < n:
			mini = min(mini, abs(a[i + 1] - a[i]))
		maxi = max(maxi, mini)
	print(maxi)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	max1 = 0
	for i in range(len(l)):
		if i == 0:
			dist = abs(l[i + 1] - l[i])
			max1 = max(dist, max1)
		elif i == len(l) - 1:
			dist = abs(l[i] - l[i - 1])
			max1 = max(dist, max1)
		else:
			dist = min(abs(l[i + 1] - l[i]), abs(l[i] - l[i - 1]))
			max1 = max(dist, max1)
	print(max1)