We have n cards with each card numbered from 1 to n. All cards are randomly shuffled. We are allowed only operation moveCard(n) which moves the card with value n to the top of the pile. You are required to find out the minimum number of moveCard() operations required to sort the cards in increasing order.
 
Example 1:
Input:
n  = 5
a[] = {5, 1, 2, 3, 4}
Output:
4
Explanation:
5 1 2 3 4              //given sequence
4 5 1 2 3              //moveCard(4)
3 4 5 1 2              //moveCard(3)
2 3 4 5 1              //moveCard(2)
1 2 3 4 5              //moveCard(1)
Hence, minimum 4 operations are required.
 
Example 2:
Input:
n = 4
a[] = {3, 4, 2, 1}
Output:
2
Explanation:
3 4 2 1             //given sequence
2 3 4 1             //moveCard(2)
1 2 3 4             //moveCard(1)
Hence, minimum 2 operations are required.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minOps() which takes the array a[] and its size n as inputs and returns the minimum number of operations required.
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= n <=10^{7} 
1 <= a[i] <= n

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



def minOps( a, n):

    

    

    



Solutions:
def minOps(a, n):
	stack = []
	a.reverse()
	for item in a:
		while stack and stack[-1] < item:
			stack.pop()
		stack.append(item)
	i = 1
	while i < len(stack) and stack[i] + 1 == stack[i - 1]:
		i += 1
	return n - i


def minOps(a, n):
	a.reverse()
	stack = []
	for item in a:
		while stack and stack[-1] < item:
			stack.pop()
		stack.append(item)
	count = 1
	for i in range(len(stack) - 1):
		if stack[i + 1] == stack[i] - 1:
			count += 1
		else:
			break
	return n - count


def minOps(a, n):
	j = n
	for i in range(n - 1, -1, -1):
		if a[i] == j:
			j -= 1
	return j


def minOps(a, n):
	count = 0
	t = n
	for i in range(len(a) - 1, -1, -1):
		if a[i] == t:
			count += 1
			t -= 1
	return n - count


def minOps(a, n):
	count = n
	for i in range(n - 1, -1, -1):
		if a[i] == count:
			count -= 1
	return count


def minOps(a, n):
	check = n
	count = 0
	for i in reversed(range(len(a))):
		if a[i] == check:
			count += 1
			check -= 1
	return n - count


def minOps(a, n):
	check = n
	count = 0
	for i in reversed(range(len(a))):
		if a[i] == check:
			count += 1
			check -= 1
	return n - count

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


def minOps(a, n):
	val = n
	i = n - 1
	while i >= 0:
		if a[i] == val:
			val -= 1
		i -= 1
	return val


def minOps(a, n):
	expectedNextNumber = n
	countOfAlreadySortedNumbers = 0
	for item in range(n - 1, -1, -1):
		if expectedNextNumber == a[item]:
			countOfAlreadySortedNumbers += 1
			expectedNextNumber = a[item] - 1
	return n - countOfAlreadySortedNumbers


def minOps(a, n):
	expectedNumber = n
	countOfSorted = 0
	for i in range(n - 1, -1, -1):
		if expectedNumber == a[i]:
			countOfSorted += 1
			expectedNumber = a[i] - 1
	return n - countOfSorted


def minOps(a, n):
	last_val = a[-1]
	des_val = n
	count = 0
	for i in range(n, 0, -1):
		if a[i - 1] == des_val:
			count += 1
			des_val -= 1
	return n - count