Given an array nums[] of N positive integers. Find the minimum number of operations required to modify the array such that array elements are in strictly increasing order (A[i] < A[i+1]).
Changing a number to greater or lesser than original number is counted as one operation.
Example 1:
Input: nums[] = [1, 2, 3, 6, 5, 4]
Output: 2
Explanation: By decreasing 6 by 2 and
increasing 4 by 2, arr will be like
[1, 2, 3, 4, 5, 6] which is stricly 
increasing.
Example 2:
Input: nums[] = [1, 2, 3, 4]
Output: 0
Explanation: Arrays is already strictly
increasing.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function min_opeartions() which takes the array nums[] as input parameter and returns the minimum number of opeartion needed to make the array strictly increasing.
 
Expected Time Complexity: O(n^2)
Expected Space Complexity: O(n)
 
Constraints: 
1 <= length of array <= 1000
1 <= arr[i] <= 1000000

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
	def min_operations(self,nums):
		# Code here

Solutions:
from bisect import bisect_right

class Solution:

	def min_operations(self, nums):
		for i in range(len(nums)):
			nums[i] -= i
		lis = []
		for i in range(len(nums)):
			pos = bisect_right(lis, nums[i])
			if pos == len(lis):
				lis.append(nums[i])
			else:
				lis[pos] = nums[i]
		return len(nums) - len(lis)


class Solution:

	def min_operations(self, nums):
		N = len(nums)
		dp = [1] * N
		for i in range(1, N):
			for j in range(i):
				if nums[i] - nums[j] >= i - j:
					dp[i] = max(dp[i], dp[j] + 1)
		return N - max(dp)


class Solution:

	def min_operations(self, a):
		n = len(a)
		dp = [1] * n
		for i in range(n):
			for j in range(i):
				if a[i] > a[j] and a[i] - a[j] >= i - j:
					dp[i] = max(dp[i], dp[j] + 1)
		return n - max(dp)


class Solution:

	def min_operations(self, nums):
		n = len(nums)
		dp = [1] * n
		ans = 1
		for i in range(1, n):
			maxi = 0
			for j in range(i):
				if nums[j] + (i - j) <= nums[i]:
					maxi = max(maxi, dp[j])
			dp[i] = 1 + maxi
			ans = max(ans, dp[i])
		return n - ans


class Solution:

	def LIS(self, arr, n):
		res = [1] * n
		for i in range(1, n):
			for j in range(i):
				if arr[j] < arr[i] and arr[i] - arr[j] >= i - j:
					res[i] = max(res[i], res[j] + 1)
		return res

	def min_operations(self, nums):
		n = len(nums)
		lis = self.LIS(nums, n)
		return n - max(lis)


class Solution:

	def min_operations(self, arr):
		n = len(arr)
		if n == 1:
			return 0
		LIS = [0 for i in range(n)]
		le = 0
		for i in range(n):
			LIS[i] = 1
		for i in range(1, n):
			for j in range(i):
				if arr[i] > arr[j] and i - j <= arr[i] - arr[j]:
					LIS[i] = max(LIS[i], LIS[j] + 1)
			le = max(le, LIS[i])
		return n - le


from math import inf

class Solution:

	def min_operations(self, x):
		l = len(x)

		def f(i, p):
			if i == l:
				return 0
			if (i, p) in dp:
				return dp[i, p]
			ans = 1 + f(i + 1, p + 1)
			if x[i] > p:
				ans = min(ans, f(i + 1, x[i]))
			dp[i, p] = ans
			return ans
		dp = {}
		return min(f(1, x[0]), 1 + f(1, -10 ** 8))


from bisect import *

class Solution:

	def min_operations(self, nums):

		def lis(arr):
			n = len(arr)
			lis = [1] * n
			for i in range(1, n):
				for j in range(0, i):
					if arr[i] >= arr[j] + (i - j) and lis[i] < lis[j] + 1:
						lis[i] = lis[j] + 1
			maximum = 0
			for i in range(n):
				maximum = max(maximum, lis[i])
			return maximum
		l = lis(nums)
		n = len(nums)
		return n - l


class Solution:

	def min_operations(self, nums):
		arr = nums
		l = len(arr)
		if l == 1:
			return 0
		LIS = [0 for i in range(l)]
		lent = 0
		for i in range(l):
			LIS[i] = 1
		for i in range(1, l):
			for j in range(i):
				if arr[i] > arr[j] and i - j <= arr[i] - arr[j]:
					LIS[i] = max(LIS[i], LIS[j] + 1)
			lent = max(lent, LIS[i])
		return l - lent


class Solution:

	def min_operations(self, nums):
		n = len(nums)
		ans = 1
		lis = [1 for i in range(n)]
		for i in range(1, n):
			for j in range(i):
				if nums[i] > nums[j] and i - j <= nums[i] - nums[j]:
					lis[i] = max(lis[i], lis[j] + 1)
			ans = max(ans, lis[i])
		return n - ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.min_operations(nums)
		print(ans)


class Solution:

	def min_operations(self, nums):
		dp = [1 for i in range(len(nums))]
		maxi = 1
		for i in range(len(nums)):
			for prev in range(i):
				if nums[prev] < nums[i] and i - prev <= nums[i] - nums[prev] and (1 + dp[prev] > dp[i]):
					dp[i] = 1 + dp[prev]
			if maxi < dp[i]:
				maxi = dp[i]
		return len(nums) - maxi


class Solution:

	def min_operations(self, nums):
		n = len(nums)
		ans = 1
		lis = [1 for i in range(n)]
		for i in range(1, n):
			for j in range(i):
				if nums[i] > nums[j] and i - j <= nums[i] - nums[j]:
					lis[i] = max(lis[i], lis[j] + 1)
			ans = max(ans, lis[i])
		return n - ans


class Solution:

	def min_operations(self, nums):
		N = len(nums)
		soln = [1] * N
		for i in range(1, N):
			for j in range(0, i):
				if nums[i] > nums[j] and i - j <= nums[i] - nums[j]:
					soln[i] = max(soln[i], 1 + soln[j])
		return N - max(soln)


from bisect import bisect_left

class Solution:

	def min_operations(self, arr):
		l = 1
		n = len(arr)
		dp = [1] * n
		for i in range(1, n):
			m = 1
			for j in range(i):
				if arr[j] < arr[i] and i - j <= arr[i] - arr[j] and (dp[j] + 1 > m):
					m = dp[j] + 1
			dp[i] = m
			if l < m:
				l = m
		return n - l


class Solution:

	def bsearch(self, arr, num):
		(l, r) = (0, len(arr) - 1)
		while r - l > 1:
			mid = (l + r) // 2
			if arr[mid] == num:
				l = mid
			elif arr[mid] > num:
				r = mid
			else:
				l = mid
		if num == arr[r]:
			return r + 1
		if num == arr[l]:
			return l + 1
		if num > arr[r]:
			return r + 1
		if num < arr[l]:
			return l
		return r

	def lengthOfLIS(self, nums):
		if not nums:
			return 0
		store = [nums[0]]
		for num in nums[1:]:
			idx = self.bsearch(store, num)
			if idx == len(store):
				store.append(num)
			else:
				store[idx] = num
		return len(store)

	def min_operations(self, nums):
		n = len(nums)
		new_nums = [nums[i] - i for i in range(n)]
		l = self.lengthOfLIS(new_nums)
		return n - l


import heapq

class Solution:

	def mod(nums):
		n = len(nums)
		dp = [-1 for i in range(n)]
		dp[0] = 1
		for i in range(1, n):
			dp[i] = 1
			for j in range(i - 1, -1, -1):
				if nums[i] <= nums[j]:
					continue
				if i - j <= nums[i] - nums[j]:
					dp[i] = max(dp[i], 1 + dp[j])
		return max(dp)

	def min_operations(self, nums):
		return len(nums) - Solution.mod(nums)


class Solution:

	def min_operations(self, nums):
		if len(nums) == 1:
			return 0
		lis = [1 for i in range(len(nums))]
		max1 = 0
		for i in range(1, len(nums)):
			for j in range(0, i):
				if nums[i] > nums[j] and i - j <= nums[i] - nums[j]:
					lis[i] = max(lis[i], lis[j] + 1)
			max1 = max(max1, lis[i])
		return len(nums) - max1


class Solution:

	def min_operations(self, nums):
		n = len(nums)
		LIS = [0 for i in range(n)]
		z = 0
		for i in range(n):
			LIS[i] = 1
		for i in range(1, n):
			for j in range(i):
				if nums[i] > nums[j] and i - j <= nums[i] - nums[j]:
					LIS[i] = max(LIS[i], LIS[j] + 1)
			z = max(z, LIS[i])
		if n == 1:
			return 0
		return n - z


def SIA(arr):
	dp = [1 for i in arr]
	for i in range(1, len(arr)):
		for j in range(i):
			if arr[i] > arr[j] and i - j <= arr[i] - arr[j]:
				dp[i] = max(dp[i], 1 + dp[j])
	return len(arr) - max(dp)

class Solution:

	def min_operations(self, nums):
		return SIA(nums)


class Solution:

	def min_operations(self, nums):
		arr = nums.copy()
		n = len(nums)
		LIS = [0 for i in range(n)]
		len1 = 0
		for i in range(n):
			LIS[i] = 1
		for i in range(1, n):
			for j in range(i):
				if arr[i] > arr[j] and i - j <= arr[i] - arr[j]:
					LIS[i] = max(LIS[i], LIS[j] + 1)
		return n - max(LIS)