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$

Difficulty: interview

Starter code:

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()

# cook your dish here

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)