Given an array arr of size N, the task is to remove or delete the minimum number of elements from the array so that when the remaining elements are placed in the same sequence order form an increasing sorted sequence.
Example 1:
Input: N = 5, arr[] = {5, 6, 1, 7, 4}
Output: 2
Explanation: Removing 1 and 4
leaves the remaining sequence order as
5 6 7 which is a sorted sequence.
 
Example 2:
Input: N = 3, arr[] = {1, 1, 1}
Output: 2
Explanation: Remove 2 1's
Your Task:  
You don't need to read input or print anything. Complete the function minDeletions() 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 minDeletions(self, arr, n):
		# code here

Solutions:
from bisect import bisect_left

class Solution:

	def minDeletions(self, arr, n):
		lis = [arr[0]]
		for num in arr:
			if num > lis[-1]:
				lis.append(num)
			else:
				idx = bisect_left(lis, num)
				lis[idx] = num
		return n - len(lis)


class Solution:

	def BS(self, tail, l, r, x):
		while r > l:
			mid = l + (r - l) // 2
			if tail[mid] >= x:
				r = mid
			else:
				l = mid + 1
		return r

	def minDeletions(self, a, n):
		lis = []
		lis.append(a[0])
		length = 1
		for i in range(1, n):
			if a[i] > lis[length - 1]:
				lis.append(a[i])
				length += 1
			else:
				index = self.BS(lis, 0, length - 1, a[i])
				lis[index] = a[i]
		return n - length


class Solution:

	def minDeletions(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


from bisect import bisect_left

class Solution:

	def minDeletions(self, arr, n):
		subset = [arr[0]]
		for item in arr[1:]:
			if item > subset[-1]:
				subset.append(item)
			else:
				i = bisect_left(subset, item)
				subset[i] = item
		return n - len(subset)


class Solution:

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


class Solution:

	def minDeletions(self, arr, n):
		opt = [1 for _ in range(n)]
		lis = 1
		for i in range(n):
			for j in range(i):
				if arr[i] > arr[j]:
					opt[i] = max(opt[i], 1 + opt[j])
					lis = max(lis, opt[i])
		return n - lis


import sys
from bisect import bisect_right as upper

class Solution:

	def minDeletions(self, arr, n):
		dp = [sys.maxsize for i in range(0, n + 1)]
		dp[0] = -sys.maxsize
		maxidx = 0
		for i in range(0, n):
			idx = upper(dp, arr[i])
			if dp[idx - 1] < arr[i] and dp[idx] > arr[i]:
				dp[idx] = arr[i]
				maxidx = max(idx, maxidx)
		return n - maxidx


class Solution:

	def minDeletions(self, arr, n):
		lis = [1] * n
		for i in range(1, n):
			for j in range(0, i):
				if arr[j] < arr[i] and lis[i] <= lis[j]:
					lis[i] = 1 + lis[j]
		maxlis = max(lis)
		mindeletions = n - maxlis
		return mindeletions


class Solution:

	def minDeletions(self, arr, n):
		import bisect
		lis = []
		count = 0
		for i in range(n):
			ind = bisect.bisect_left(lis, arr[i])
			if ind >= len(lis):
				lis.append(arr[i])
				count += 1
			else:
				lis[ind] = arr[i]
		return n - count


from bisect import bisect_left

class Solution:

	def minDeletions(self, H, N):
		ans = []
		for st in H:
			pi = bisect_left(ans, st)
			if pi >= len(ans):
				ans.append(st)
			else:
				ans[pi] = st
		return N - len(ans)


class Solution:

	def minDeletions(self, arr, n):
		cnt = 0
		val = [i for i in range(0, n)]
		for idx in range(0, n):
			val[idx] = 1
			for idx1 in range(idx - 1, -1, -1):
				if arr[idx] > arr[idx1]:
					val[idx] = max(val[idx], val[idx1] + 1)
			cnt = max(val[idx], cnt)
		return n - cnt


class Solution:

	def minDeletions(self, arr, n):
		dp = [[-1 for _ in range(len(arr) + 1)] for _ in range(len(arr) + 1)]

		def recurse(i, j):
			if j > len(arr) - 1:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			(total1, total2) = (0, 0)
			if i == -1 or arr[j] > arr[i]:
				total1 = recurse(j, j + 1) + 1
			total2 = recurse(i, j + 1)
			dp[i][j] = max(total1, total2)
			return dp[i][j]
		lis_len = recurse(-1, 0)
		return len(arr) - lis_len


class Solution:

	def minDeletions(self, arr, n):
		dp = [[-1 for j in range(0, n + 1)] for i in range(0, n)]

		def solve(idx, prev):
			if idx == n:
				return 0
			if dp[idx][prev + 1] != -1:
				return dp[idx][prev + 1]
			exclude = solve(idx + 1, prev)
			include = 0
			if prev == -1 or arr[idx] > arr[prev]:
				include = 1 + solve(idx + 1, idx)
			dp[idx][prev + 1] = max(include, exclude)
			return dp[idx][prev + 1]
		maxlis = solve(0, -1)
		return n - maxlis


class Solution:

	def minDeletions(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)


class Solution:

	def minDeletions(self, arr, N):
		dp = [1 for _ in range(N)]
		res = 1
		for i in range(1, N):
			for j in range(i):
				if arr[i] > arr[j] and dp[i] < dp[j] + 1:
					dp[i] = 1 + dp[j]
					if dp[i] > res:
						res = dp[i]
		return N - res


from bisect import bisect_left

class Solution:

	def minDeletions(self, arr, n):
		st = []
		for i in arr:
			if not st or st[-1] < i:
				st.append(i)
			else:
				idx = bisect_left(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.minDeletions(arr, n)
		print(ans)


class Solution:

	def minDeletions(self, arr, n):
		lis = [1] * n
		for i in range(1, n):
			for j in range(0, i):
				if arr[j] < arr[i] and lis[i] <= lis[j]:
					lis[i] = 1 + lis[j]
		goodItems = max(lis)
		ItemsNeedtoremove = n - goodItems
		return ItemsNeedtoremove
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.minDeletions(arr, n)
		print(ans)


class Solution:

	def lower_bound(self, arr, key):
		low = 0
		n = len(arr)
		high = n - 1
		ans = n
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] >= key:
				high = mid - 1
				ans = mid
			else:
				low = mid + 1
		return ans

	def lis_util(self, arr, n):
		lis = [arr[0]]
		for i in range(1, n):
			if arr[i] > lis[-1]:
				lis.append(arr[i])
			else:
				lis[self.lower_bound(lis, arr[i])] = arr[i]
		return len(lis)

	def minDeletions(self, arr, n):
		return n - self.lis_util(arr, n)
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.minDeletions(arr, n)
		print(ans)


class Solution:

	def minDeletions(self, arr, n):
		t = [1 for i in range(n)]
		for i in range(1, n):
			for j in range(i):
				if arr[i] > arr[j] and t[i] <= t[j]:
					t[i] = t[j] + 1
		return n - max(t)
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.minDeletions(arr, n)
		print(ans)


class Solution:

	def minDeletions(self, a, n):
		b = sorted(set(a))
		dp = {}

		def r(m=len(a), n=len(b)):
			if m == 0 or n == 0:
				return 0
			if (m, n) in dp:
				return dp[m, n]
			if a[m - 1] == b[n - 1]:
				dp[m, n] = 1 + r(m - 1, n - 1)
				return dp[m, n]
			else:
				dp[m, n] = max(r(m - 1, n), r(m, n - 1))
				return dp[m, n]
		return len(a) - r()


class Solution:

	def minDeletions(self, arr, n):
		dp = [1 for i in range(len(arr))]
		for i in range(1, len(arr)):
			for k in range(0, i):
				if arr[k] < arr[i]:
					dp[i] = max(dp[i], 1 + dp[k])
		return len(arr) - max(dp)


class Solution:

	def minDeletions(self, nums, n):

		def ceilIdx(tail, l, r, x):
			while r > l:
				m = l + (r - l) // 2
				if tail[m] >= x:
					r = m
				else:
					l = m + 1
			return r
		lenn = 1
		tail = [0] * n
		tail[0] = nums[0]
		for i in range(1, n):
			if nums[i] > tail[lenn - 1]:
				tail[lenn] = nums[i]
				lenn += 1
			else:
				c = ceilIdx(tail, 0, lenn - 1, nums[i])
				tail[c] = nums[i]
		return n - lenn
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.minDeletions(arr, n)
		print(ans)


class Solution:

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


class Solution:

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


from collections import Counter

class Solution:

	def minDeletions(self, arr, n):

		def bs(a, e):
			(l, h) = (0, len(a) - 1)
			while l <= h:
				m = (l + h) // 2
				if a[m] == e:
					return m
				elif a[m] < e:
					l = m + 1
				else:
					h = m - 1
			return l
		dp = [arr[0]]
		for i in range(1, len(arr)):
			if arr[i] > dp[-1]:
				dp.append(arr[i])
			else:
				dp[bs(dp, arr[i])] = arr[i]
		return len(arr) - len(dp)


class Solution:

	def minDeletions(self, arr, n):
		data = [1 for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, i):
				if arr[i - 1] > arr[j - 1]:
					data[i] = max(data[i], data[j] + 1)
		return n - max(data)


class Solution:

	def minDeletions(self, nums, n):
		arr = [1 for i in range(len(nums))]
		j = 1
		while j < len(nums):
			for i in range(j):
				if nums[i] < nums[j] and arr[j] <= arr[i]:
					arr[j] = 1 + arr[i]
			j += 1
		return n - max(arr)


class Solution:

	def minDeletions(self, nums, n):

		def ceilIdx(tail, l, r, x):
			while r > l:
				m = l + (r - l) // 2
				if tail[m] >= x:
					r = m
				else:
					l = m + 1
			return r
		lenn = 1
		tail = [0] * n
		tail[0] = nums[0]
		for i in range(1, n):
			if nums[i] > tail[lenn - 1]:
				tail[lenn] = nums[i]
				lenn += 1
			else:
				c = ceilIdx(tail, 0, lenn - 1, nums[i])
				tail[c] = nums[i]
		return n - lenn


class Solution:

	def minDeletions(self, nums, n):

		def binary(temp, l, r, target):
			while r >= l:
				mid = (l + r) // 2
				if temp[mid] == target:
					return mid
				elif temp[mid] > target:
					r = mid - 1
				else:
					l = mid + 1
			return l
		temp = [nums[0]]
		for i in range(1, len(nums)):
			if nums[i] > temp[-1]:
				temp.append(nums[i])
			else:
				indx = binary(temp, 0, len(temp) - 1, nums[i])
				temp[indx] = nums[i]
		return n - len(temp)


class Solution:

	def recur(self, i, j, a):
		global dp
		if i >= j:
			return 0
		if a[i] < a[j]:
			dp[i][j] = self.recur(i + 1, j - 1, a)
			return dp[i][j]
		rl = 1 + self.recur(i + 1, j, a)
		rr = 1 + self.recur(i, j - 1, a)
		dp[i][j] = min(rl, rr)
		return dp[i][j]

	def minDeletions(self, a, n):
		if n == 1:
			return 0
		dp = [1 for i in range(n)]
		lis = 1
		for i in range(1, n):
			for j in range(i):
				if a[i] > a[j]:
					dp[i] = max(dp[i], 1 + dp[j])
					lis = max(lis, dp[i])
		return n - lis


class Solution:

	def minDeletions(self, arr, n):
		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 minDeletions(self, arr, n):
		dp = [0 for _ in range(n)]
		dp[0] = 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)
		Max = 0
		for i in range(n):
			Max = max(Max, dp[i])
		return n - Max


class Solution:

	def minDeletions(self, arr, n):
		lics = [1] * n
		for i in range(n):
			for j in range(i):
				if arr[j] < arr[i]:
					lics[i] = max(lics[i], lics[j] + 1)
		ans = lics[0]
		for i in range(n):
			ans = max(ans, lics[i])
		return n - ans


class Solution:

	def minDeletions(self, arr, n):

		def BS(ar, h, val):
			l = 0
			if ar[l] >= val:
				return l
			if ar[h] >= val and ar[h - 1] < val:
				return h
			while l < h:
				md = (l + h) // 2
				if ar[md - 1] < val and ar[md] >= val:
					return md
				if ar[md] < val and ar[md + 1] >= val:
					return md + 1
				if ar[md] < val:
					l = md + 1
				else:
					h = md - 1
			return -1

		def LIS(arr, n):
			ar = [arr[0]]
			for i in range(1, n):
				if arr[i] > ar[-1]:
					ar.append(arr[i])
				else:
					pos = BS(ar, len(ar) - 1, arr[i])
					ar[pos] = arr[i]
			return len(ar)
		return n - LIS(arr, n)


class Solution:

	def minDeletions(self, arr, n):
		brr = sorted(list(set(arr)))
		m = len(brr)
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if arr[i - 1] == brr[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return n - dp[-1][-1]


class Solution:

	def longest_increasing_subseq(self, arr, currIdx, prevIdx, mem):
		if currIdx >= len(arr):
			return 0
		if mem[currIdx][prevIdx + 1] != -1:
			return mem[currIdx][prevIdx + 1]
		case1 = case2 = 0
		if prevIdx == -1 or arr[currIdx] > arr[prevIdx]:
			case1 = 1 + self.longest_increasing_subseq(arr, currIdx + 1, currIdx, mem)
		case2 = self.longest_increasing_subseq(arr, currIdx + 1, prevIdx, mem)
		mem[currIdx][prevIdx + 1] = max(case1, case2)
		return mem[currIdx][prevIdx + 1]

	def minDeletions(self, arr, n):
		mem = [[-1 for _ in range(n)] for _ in range(n)]
		lis = self.longest_increasing_subseq(arr, 0, -1, mem)
		return n - lis


def lis(arr, n):
	result = 0
	lis = [0 for i in range(n)]
	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 lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
	for i in range(n):
		if result < lis[i]:
			result = lis[i]
	return result

def minimumNumberOfDeletions(arr, n):
	len = lis(arr, n)
	return n - len

class Solution:

	def minDeletions(self, arr, n):
		return minimumNumberOfDeletions(arr, n)


class Solution:

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


class Solution:

	def minDeletions(self, arr, n):
		lst = [1] * n
		for i in range(len(arr) - 1, -1, -1):
			for j in range(i + 1, len(arr)):
				if arr[i] < arr[j]:
					lst[i] = max(lst[i], 1 + lst[j])
		return n - max(lst)


class Solution:

	def minDeletions(self, arr, n):
		b = sorted(list(set(arr)))
		t = [[0 for i in range(n + 1)] for j in range(len(b) + 1)]
		for i in range(1, len(b) + 1):
			for j in range(1, n + 1):
				if b[i - 1] == arr[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		z = t[-1][-1]
		return n - z


class Solution:

	def minDeletions(self, a, n):
		b = sorted(list(set(a)))
		m = len(b)
		dp = [[0] * (m + 1) for j in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if a[i - 1] == b[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		ans = n - dp[-1][-1]
		return ans


class Solution:

	def minDeletions(self, arr, n):

		def check_happy_sorted_array(xlen, x):
			y = longest_increasing_subsequence(xlen, x)
			output = xlen - y
			return output

		def longest_increasing_subsequence(xlen, x):
			output = 0
			longest_increasing = [1 for i in range(xlen)]
			for i in range(1, xlen):
				for j in range(i):
					if x[i] > x[j] and longest_increasing[i] < longest_increasing[j] + 1:
						longest_increasing[i] = longest_increasing[j] + 1
			for i in range(xlen):
				if output < longest_increasing[i]:
					output = longest_increasing[i]
			return output
		return check_happy_sorted_array(n, arr)


class Solution:

	def minDeletions(self, a1, n1):
		a2 = sorted(list(set(a1)))
		n2 = len(a2)
		tab = [[0 for _ in range(n2 + 1)] for _ in range(n1 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				if a1[i - 1] == a2[j - 1]:
					tab[i][j] = 1 + tab[i - 1][j - 1]
				else:
					tab[i][j] = max(tab[i - 1][j], tab[i][j - 1])
		return n1 - tab[-1][-1]


import sys

class Solution:

	def lis(self, a, n):
		dp = [1 for i in range(n)]
		for i in range(1, n):
			for j in range(0, i):
				if a[i] > a[j]:
					dp[i] = max(dp[i], 1 + dp[j])
		len = -sys.maxsize
		for i in range(n):
			len = max(len, dp[i])
		return len

	def minDeletions(self, arr, n):
		lis = self.lis(arr, n)
		return n - lis


class Solution:

	def minDeletions(self, s, n):
		dp = [0] * (len(s) + 1)
		dp[0] = 0
		max_longest_subsequence = 0
		for i in range(1, len(dp)):
			j = i - 1
			max_num = 0
			while j > 0:
				if s[j - 1] < s[i - 1]:
					max_num = max(max_num, dp[j])
				j -= 1
			if max_num == 0:
				dp[i] = 1
			else:
				dp[i] = max_num + 1
			max_longest_subsequence = max(max_longest_subsequence, dp[i])
		return len(s) - max_longest_subsequence


class Solution:

	def minDeletions(self, arr, n):
		li = []

		def binary(ele, li):
			start = 0
			end = len(li) - 1
			while start <= end:
				mid = (start + end) // 2
				if ele == li[mid]:
					return mid
				if ele < li[mid]:
					end = mid - 1
				else:
					start = mid + 1
			return start
		for i in range(n):
			if len(li) == 0:
				li.append(arr[0])
			if li[-1] >= arr[i]:
				li[binary(arr[i], li)] = arr[i]
			else:
				li.append(arr[i])
		return n - len(li)


class Solution:

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

	def minDeletions(self, arr, n):
		m = self.LIS(arr, n)
		return n - m


class Solution:

	def minDeletions(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


class Solution:

	def minDeletions(self, arr, n):
		tail = [arr[0]]
		l = 1
		for i in range(1, n):
			if arr[i] > tail[l - 1]:
				tail.append(arr[i])
				l += 1
			else:
				c = self.bs(tail, 0, l - 1, arr[i])
				tail[c] = arr[i]
		return n - l

	def bs(self, tail, l, r, x):
		while r > l:
			m = l + (r - l) // 2
			if tail[m] >= x:
				r = m
			else:
				l = m + 1
		return r