Chef has a garden with $N$ plants arranged in a line in decreasing order of height. Initially the height of the plants are $A_1, A_2, ..., A_N$.
The plants are growing, after each hour the height of the $i$-th plant increases by $i$ millimeters. Find the minimum number of integer hours that Chef must wait to have two plants of the same height.

-----Input:-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space separated integers $A_1,A_2,..A_N$. 

-----Output:-----
For each test case print a single line containing one integer, the minimum number of integer hours that Chef must wait to have two plants of the same height.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq N \leq 10^5$
- $0\leq A_i \leq 10^{18}$
- $A_i >A_{i+1}$, for each valid $i$
- The Sum of $N$ over all test cases does not exceed $10^6$

-----Sample Input:-----
1
3
8 4 2

-----Sample Output:-----
2

-----EXPLANATION:-----
After $2$ hours there are two plants with the same height. 
$[8,4,2] \rightarrow [9,6,5] \rightarrow [10,8,8]$.

Difficulty: interview

Starter code:

Solutions:

for _ in range(int(input())):
 n = int(input())
 arr = list(map(int, input().split()))
 hrs = arr[0] - arr[1]

 for i in range(1, n-1):
  if hrs > arr[i] - arr[i+1]:
   hrs = arr[i] - arr[i+1]

 print(hrs)

# cook your dish here
for _ in range(int(input())):
 n = int(input())
 a = list(map(int,input().split()))
 ans = a[0]-a[1]
 for i in range(1,n-1):
  m = a[i]-a[i+1]
  if ans > m : ans = m
 print(ans)


# cook your dish here
for _ in range(int(input())):
 n,a,b = int(input()),list(map(int,input().split())),[]
 for i in range(n-1): b.append(a[i]-a[i+1])
 print(min(b)) 

#872//2
for _ in range(int(input())):
 n,a,b = int(input()),list(map(int,input().split())),[]
 for i in range(n-1): b.append(a[i]-a[i+1])
 print(min(b)) 

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

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


t = int(input())

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

t = int(input())
for i in range(0,t):
 n = int(input())
 A = [int(x) for x in input().split()]
 if(n>2):
  for i in range(0,n-2):
   if(i==0): result = min(A[i]-A[i+1],A[i+1]-A[i+2])
   else: result = min(result,A[i+1]-A[i+2])
 else: result = A[0]-A[1]
 print(result) 

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 k=[]
 for i in range(len(l)-1):
  j=l[i]-l[i+1]
  k.append(j)
 print(min(k))

for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 k=[]
 for i in range(len(l)-1):
  j=l[i]-l[i+1]
  k.append(j)
 print(min(k))

# cook your dish here
try:
 for _ in range(int(input())):
  n = int(input())
  l1 = list(map(int, input().split()))
  ans = [l1[i - 1] - l1[i] for i in range(1, len(l1))]
  print(min(ans))
except:
 pass

# cook your dish here
for _ in range(int(input())):
 n = int(input())
 l1 = list(map(int, input().split()))
 ans = [l1[i - 1] - l1[i] for i in range(1, len(l1))]
 print(min(ans))

def gcd(a,b):
 if a==0:
  return b
 return(gcd(b%a,a))
def lcm(a,b):
 return((a*b)/gcd(a,b))
T=int(input())
for _ in range(0,T):
 N=int(input())
 l=[]
 A=list(map(int,input().split()))
 for i in range(0,len(A)-1):
  l.append(A[i]-A[i+1])
 print(min(l))


for k in range(int(input())):
 n=int(input())
 li=list(map(int,input().split()))
 b=[]
 for g in range(len(li)-1):
  b.append(li[g]-li[g+1])
 print(min(b))

# cook your dish here
for _ in range(int(input())):
 size = int(input())
 a = [int(x) for x in input().split(" ")]
 b = []
 for i in range(len(a)-1):
  b.append(a[i]-a[i+1])
 print(min(b))


# cook your dish here
for i in range(int(input())):
 n=int(input())
 arr=list(map(int,input().split()))
 ans=arr[0]
 i=0
 while(i<n-1):
  ans=min(ans,arr[i]-arr[i+1])
  i+=1 
 print(ans)


# cook your dish here
for _ in range(int(input())):
 size = int(input())
 a = [int(x) for x in input().split(" ")]
 b = []
 for i in range(len(a)-1):
  b.append(a[i]-a[i+1])
 print(min(b))

for _ in range(int(input())):
 n=int(input())
 a=[*list(map(int,input().split()))]
 ans=100000000000000000000
 for i in range(0,len(a)-1):
  mn=a[i]-a[i+1]
  if mn<ans:
   ans=mn
 print(ans)


for _ in range(int(input())):
 lens = int(input())
 arrs = [int(x) for x in input().split()]
 ans = min([ abs(y - x) for x, y in zip(arrs, arrs[1:])])
 print(ans)

for _ in range(int(input())):
 size = int(input())
 a = [int(x) for x in input().split(" ")]
 b = []
 for i in range(len(a)-1):
  b.append(a[i]-a[i+1])
 print(min(b))



a = int(input())
while a!=0:
 b = int(input())
 mylist = list(map(int,input().split()))
 min = mylist[0]-mylist[1]
 for i in range(len(mylist)-1):
  p = mylist[i]-mylist[i+1]
  if p <min:
   min =p


 print(min)




 a-=1

for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 k=[]
 for i in range(len(l)-1):
  j=l[i]-l[i+1]
  k.append(j)
 print(min(k))