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]$.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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)


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)


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


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)


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


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


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


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


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)


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