In a given array A[] find the maximum value of (A[i] – i) - (A[j] – j) where i is not equal to j. 
i and j vary from 0 to N-1 and N is the size of input array A[].  The value of N is always greater than 1.
Example 1:
Input
N = 5
A[] = {9, 15, 4, 12, 13}
Output
12
Explanation:
(a[1]-1) - (a[2]-2) = (15-1)-(4-2) = 12
 
Example 2:
Input
N = 4
A[] = {3, 1, 2, 4}
Output
3
Explanation:
(a[1]-1) - (a[2]-2) = (3-1)-(1-2) = 3
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxVal() which takes the array A[] and its size N as inputs and returns the maximum value
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
2 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{5}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def maxVal(self, a, n):
        #Code Here
        


Solutions:
class Solution:

	def maxVal(self, a, n):
		maxval = 0
		minval = 1000000
		for i in range(n):
			maxval = max(maxval, a[i] - i)
			minval = min(minval, a[i] - i)
		return maxval - minval


class Solution:

	def maxVal(self, a, n):
		X = a[0] - 0
		Y = a[n - 1] - (n - 1)
		for i in range(1, n):
			X = max(X, a[i] - i)
		for j in range(n - 1, -1, -1):
			Y = min(Y, a[j] - j)
		return X - Y


class Solution:

	def maxVal(self, a, n):
		diff = []
		for index in range(n):
			diff.append(a[index] - index)
		diff.sort()
		return diff[-1] - diff[0]


import sys

class Solution:

	def maxVal(self, a, n):
		min_val = sys.maxsize
		max_val = -sys.maxsize - 1
		for i in range(n):
			if a[i] - i > max_val:
				max_val = a[i] - i
			if a[i] - i < min_val:
				min_val = a[i] - i
		return max_val - min_val


class Solution:

	def maxVal(self, a, n):
		mx = 0
		mn = 1000000
		ans = 0
		for i in range(0, n):
			prvmx = mx
			prvmn = mn
			if a[i] - i + 1 > mx:
				mx = a[i] - i + 1
			if a[i] - i + 1 < mn:
				mn = a[i] - i + 1
			ans = max(ans, prvmx - mn)
			ans = max(ans, mx - prvmn)
		return ans


class Solution:

	def maxVal(self, arr, N):
		maxi = arr[0] - 0
		mini = arr[0] - 0
		for i in range(1, N):
			if arr[i] - i > maxi:
				maxi = arr[i] - i
			if arr[i] - i < mini:
				mini = arr[i] - i
		return maxi - mini


class Solution:

	def maxVal(self, a, n):
		maxx = 0
		mini = 100000007
		for i in range(0, n):
			if a[i] - i > maxx:
				maxx = a[i] - i
			if a[i] - i < mini:
				mini = a[i] - i
		return maxx - mini


class Solution:

	def maxVal(self, a, n):
		for i in range(n):
			a[i] -= i
		a.sort()
		return a[-1] - a[0]


class Solution:

	def maxVal(self, a, n):
		mx = 0
		lst = []
		for i in range(n):
			lst.append(a[i] - i)
		lst.sort()
		return lst[-1] - lst[0]


class Solution:

	def maxVal(self, a, n):
		mini = 1000000000.0
		maxi = -1000000000.0
		for i in range(0, n):
			a[i] = a[i] - i
			mini = min(mini, a[i])
			maxi = max(maxi, a[i])
		return maxi - mini


class Solution:

	def maxVal(self, a, n):
		(min, max) = (99999999, -9999999)
		for i in range(0, n):
			if a[i] - i > max:
				max = a[i] - i
			if a[i] - i < min:
				min = a[i] - i
		return max - min


class Solution:

	def maxVal(self, arr, n):
		maxval = 0
		minval = float('inf')
		for i in range(n):
			maxval = max(maxval, arr[i] - i)
			minval = min(minval, arr[i] - i)
		return maxval - minval


class Solution:

	def maxVal(self, a, n):
		maxi = a[0]
		mini = a[0]
		for i in range(n):
			if a[i] - i > maxi:
				maxi = a[i] - i
			if a[i] - i < mini:
				mini = a[i] - i
		return maxi - mini


class Solution:

	def maxVal(self, a, n):
		max = a[0]
		min = a[0]
		for i in range(n):
			value = a[i] - i
			if value > max:
				max = a[i] - i
			if value < min:
				min = a[i] - i
		return max - min


class Solution:

	def maxVal(self, a: list, n: int) -> int:
		(minimum, maximum) = (float('inf'), float('-inf'))
		for i in range(n):
			if a[i] - i < minimum:
				minimum = a[i] - i
			if a[i] - i > maximum:
				maximum = a[i] - i
		return maximum - minimum


class Solution:

	def maxVal(self, a, n):
		maxa = -9999999999
		mina = 99999999999
		for i in range(0, n):
			maxa = max(maxa, a[i] - i)
			mina = min(mina, a[i] - i)
		return maxa - mina


class Solution:

	def maxVal(self, a, n):
		maxval = -999999999
		minval = 999999999
		for i in range(n):
			maxval = max(maxval, a[i] - i)
			minval = min(minval, a[i] - i)
		return maxval - minval


class Solution:

	def maxVal(self, a, n):
		s = set()
		for i in range(n):
			s.add(a[i] - i)
		return max(s) - min(s)


class Solution:

	def maxVal(self, a, n):
		dic = {}
		for i in range(n):
			k = a[i] - i
			dic[k] = True
		k = list(dic.keys())
		return max(k) - min(k)


class Solution:

	def maxVal(self, a, n):
		for i in range(n):
			a[i] = a[i] - i
		return max(a) - min(a)


class Solution:

	def maxVal(self, A, n):
		(maxi, mini) = (0, 10000000)
		for i in range(n):
			maxi = max(maxi, A[i] - i)
			mini = min(mini, A[i] - i)
		return maxi - mini


class Solution:

	def maxVal(self, a, n):
		maxi = -1
		mini = 200000
		for i in range(n):
			if a[i] - i > maxi:
				maxi = a[i] - i
			if a[i] - i < mini:
				mini = a[i] - i
		return maxi - mini


class Solution:

	def maxVal(self, a, n):
		m1 = -10 ** 5
		m2 = 10 ** 5
		for i in range(n):
			m1 = max(m1, a[i] - i)
			m2 = min(m2, a[i] - i)
		return m1 - m2


class Solution:

	def maxVal(self, a, n):
		max1 = a[0]
		min1 = a[0]
		for i in range(n):
			if a[i] - i > max1:
				max1 = a[i] - i
			if a[i] - i < min1:
				min1 = a[i] - i
		return max1 - min1


class Solution:

	def maxVal(self, a, n):
		max_val = -123456789
		min_val = 123456789
		for i in range(n):
			if a[i] - i > max_val:
				max_val = a[i] - i
			if a[i] - i < min_val:
				min_val = a[i] - i
		return max_val - min_val


class Solution:

	def maxVal(self, a, n):
		x = -999
		y = 999
		for i in range(n):
			x = max(x, a[i] - i)
			y = min(y, a[i] - i)
		return x - y


class Solution:

	def maxVal(self, a, n):
		max = -1
		min = 9999999
		for i in range(n):
			if a[i] - i > max:
				max = a[i] - i
		for i in range(n):
			if a[i] - i < min:
				min = a[i] - i
		return max - min

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.maxVal(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def maxVal(self, a, n):
		maxi = 0
		arr = [a[i] - i for i in range(n)]
		arr.sort()
		return arr[-1] - arr[0]

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.maxVal(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def maxVal(self, arr, n):
		max_n = -383736346
		min_n = 28283473433
		for i in range(0, len(arr)):
			if arr[i] - (i + 1) > max_n:
				max_n = arr[i] - (i + 1)
			if arr[i] - (i + 1) < min_n:
				min_n = arr[i] - (i + 1)
		return max_n - min_n

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.maxVal(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def maxVal(self, a, n):
		ma = -9999
		mi = 9999
		for i in range(n):
			ma = max(ma, a[i] - i)
			mi = min(mi, a[i] - i)
		return ma - mi


class Solution:

	def maxVal(self, a, n):
		(mn, mx) = (float('inf'), -float('inf'))
		for (i, x) in enumerate(a):
			mn = min(mn, x - i)
			mx = max(mx, x - i)
		return mx - mn


class Solution:

	def maxVal(self, a, n):
		MAX = -100000000000.0
		MIN = 100000000000.0
		for i in range(n):
			MAX = max(MAX, a[i] - i)
			MIN = min(MIN, a[i] - i)
		return MAX - MIN


class Solution:

	def maxVal(self, a, n):
		max = a[0] - 0
		min = a[0] - 0
		n = len(a)
		for i in range(1, n):
			x = a[i] - i
			if x < min:
				min = x
			if x > max:
				max = x
		return max - min


class Solution:

	def maxVal(self, a, n):
		for i in range(n):
			a[i] = a[i] - i
		m1 = max(a)
		m2 = min(a)
		m3 = m1 - m2
		return m3


import sys

class Solution:

	def maxVal(self, a, n):
		if n < 2:
			print('erro ')
			return 0
		min_value = sys.maxsize
		max_value = -sys.maxsize - 1
		for i in range(n):
			if a[i] - i > max_value:
				max_value = a[i] - i
			if a[i] - i < min_value:
				min_value = a[i] - i
		return max_value - min_value


class Solution:

	def maxVal(self, a, n):
		sub = []
		for i in range(n):
			sub.append(a[i] - i)
		sub.sort()
		maxD = sub[-1] - sub[0]
		return maxD


class Solution:

	def maxVal(self, a, n):
		mini = float('inf')
		maxi = float('-inf')
		for (i, val) in enumerate(a):
			if val - i < mini:
				mini = val - i
			if val - i > maxi:
				maxi = val - i
		return maxi - mini


class Solution:

	def maxVal(self, a, n):
		maxv = -float('inf')
		minv = float('inf')
		for i in range(n):
			maxv = max(maxv, a[i] - i)
			minv = min(minv, a[i] - i)
		return maxv - minv


class Solution:

	def maxVal(self, a, n):
		na = []
		for i in range(0, n):
			na.append(a[i] - i)
		qmax = 0
		qmin = 100000
		for i in range(0, n):
			if na[i] > qmax:
				qmax = na[i]
		for i in range(0, n):
			if na[i] < qmin:
				qmin = na[i]
		return qmax - qmin


class Solution:

	def maxVal(self, a, n):
		arr_1 = []
		for i in range(0, n):
			arr_1.append(a[i] - i)
		return max(arr_1) - min(arr_1)


class Solution:

	def maxVal(self, a, n):
		z = 0
		b = max(a)
		for i in range(len(a)):
			if a[i] - i > z:
				z = a[i] - i
			if a[i] - i < b:
				b = a[i] - i
		return z - b


class Solution:

	def maxVal(self, a, n):
		minv = 2 ** 31
		maxv = -2 ** 31
		for i in range(len(a)):
			minv = min(minv, a[i] - i)
			maxv = max(maxv, a[i] - i)
		return maxv - minv


import sys

class Solution:

	def maxVal(self, a, n):
		if n < 2:
			return 0
		max = -sys.maxsize - 1
		min = sys.maxsize
		for i in range(n):
			if a[i] - i > max:
				max = a[i] - i
			if a[i] - i < min:
				min = a[i] - i
		return max - min


class Solution:

	def maxVal(self, a, n):
		(maxi, mini) = (-10 ** 9, 10 ** 9)
		for (i, j) in enumerate(a):
			maxi = max(maxi, j - i)
			mini = min(mini, j - i)
		return maxi - mini


class Solution:

	def maxVal(self, a, n):
		mx = -1
		mn = 10000000
		for i in range(n):
			a[i] = a[i] - i
		return max(a) - min(a)