Given an array arr of size N, the task is to sort this array in a minimum number of steps where in one step you can remove any array element from its position and insert it in any other position.
Example 1:
Input:
N = 7
arr[] = {2, 3, 5, 1, 4, 7, 6}
Output: 3
Explanation: 
We can sort above array in 3 insertion 
steps as shown below,
1 before array value 2
4 before array value 5
6 before array value 7
Example 2:
Input:
N = 4
arr[] = {4, 6, 5, 1}
Output: 2
Explanation: 
We can sort above array in 2 insertion 
steps as shown below, 
1 before array value 4
6 after array value 5 
Your Task:  
You don't need to read input or print anything. Complete the function minInsertions() which takes N and array arr as input parameters and returns the integer value
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def minInsertions(self,arr, N):
		# code here

Solutions:
class Solution:

	def minInsertions(self, arr, N):
		dp = [1] * N
		m = 1
		for i in range(1, N):
			for j in range(i):
				if arr[j] <= arr[i]:
					dp[i] = max(dp[i], dp[j] + 1)
			m = max(m, dp[i])
		return N - m


class Solution:

	def minInsertions(self, arr, N):
		sub_arrays = [arr[0]]
		for item in arr[1:]:
			if item < sub_arrays[0]:
				sub_arrays[0] = item
			elif item >= sub_arrays[-1]:
				sub_arrays.append(item)
			else:
				for i in range(len(sub_arrays) - 1):
					if sub_arrays[i] <= item < sub_arrays[i + 1]:
						sub_arrays[i + 1] = item
						break
		return N - len(sub_arrays)


class Solution:

	def minInsertions(self, arr, n):
		import bisect
		lis = []
		for i in arr:
			ind = bisect.bisect_right(lis, i)
			if ind >= len(lis) or lis[ind] == i:
				lis.append(i)
			else:
				lis[ind] = i
		return n - len(lis)


class Solution:

	def minInsertions(self, arr, N):
		return N - self.lis(arr, N)

	def lis(self, arr, N):
		res = 0
		dp = [-1 for i in range(N + 1)]
		for i in range(N):
			dp[i] = 1
			for j in range(i):
				if arr[j] <= arr[i]:
					dp[i] = max(dp[i], dp[j] + 1)
			res = max(res, dp[i])
		return res


class Solution:

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


from bisect import bisect_right

class Solution:

	def minInsertions(self, arr, N):
		st = []
		for i in arr:
			if not st or i >= st[-1]:
				st.append(i)
			else:
				idx = bisect_right(st, i)
				st[idx] = i
		return N - len(st)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		Arr = [int(x) for x in input().split()]
		ob = Solution()
		ans = ob.minInsertions(Arr, n)
		print(ans)


class Solution:

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

	def minInsertions(self, arr, N):
		return len(arr) - self.solve(arr)


class Solution:

	def minInsertions(self, arr, n):
		dp = [1] * len(arr)
		result = 1
		for i in range(len(arr)):
			for j in range(i):
				if arr[i] >= arr[j] and dp[j] + 1 > dp[i]:
					dp[i] = dp[j] + 1
					result = max(result, dp[i])
		return n - result
		memo = {}
		n = len(arr)

		def helper(indx, prev):
			if (indx, prev) in memo:
				return memo[indx, prev]
			if indx == n:
				return 0
			nottake = helper(indx + 1, prev)
			take = 0
			if prev == -1 or arr[indx] >= arr[prev]:
				take = 1 + helper(indx + 1, indx)
			memo[indx, prev] = max(take, nottake)
			return memo[indx, prev]
		return n - helper(0, -1)


class Solution:

	def minInsertions(self, arr, n):
		dp = [1 for i in range(n)]
		for i in range(1, n):
			for j in range(0, i):
				if arr[i] >= arr[j] and dp[i] < dp[j] + 1:
					dp[i] = dp[j] + 1
		mx = 0
		for i in range(n):
			mx = max(mx, dp[i])
		return n - mx


class Solution:

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


class Solution:

	def minInsertions(self, lst, N):
		if n == 1:
			return 0
		dp = [0] * n
		dp[0] = 1
		count = 0
		for i in range(1, n):
			maxi = 0
			for j in range(i):
				if lst[i] - lst[j] >= 0:
					if dp[j] > maxi:
						maxi = dp[j]
			dp[i] = 1 + maxi
			if dp[i] > count:
				count = dp[i]
		return n - count