Given an array arr[] of size n such that array elements are distinct and in the range from 1 to n. The task is to count minimum number of move-to-front operations to arrange items as {1, 2, 3,… n}. The "move-to-front" operation is to pick any element arr[i] and place it at first position.
Example 1:
Input:
N=4
arr[] = {3, 2, 1, 4} 
Output: 2
Explanation:
We need to perform "move-to-front" on 1 
and 2 to make the array sorted.             
Example 2:
Input:
N=7
arr[] = {5, 7, 4, 3, 2, 6, 1} 
Output: 6
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function minMoves() that takes array a and n as parameters and return the minimum number of move to front operation to sort the array.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def minMoves(self,arr, n): 
        #code here.

Solutions:
class Solution:

	def minMoves(self, arr, n):
		j = n
		count = 0
		i = n - 1
		while i >= 0:
			if arr[i] == j:
				count += 1
				j -= 1
			i -= 1
		return j


class Solution:

	def minMoves(self, arr, n):
		item = n
		for i in range(n - 1, -1, -1):
			if arr[i] == item:
				item -= 1
		return item


class Solution:

	def minMoves(self, arr, n):
		ind = arr.index(n)
		num = n
		result = n - 1 - ind
		for i in range(ind, -1, -1):
			if arr[i] == num - 1:
				if i != 0:
					result += arr.index(num) - i - 1
					num = arr[i]
				else:
					result += arr.index(num) - i - 1
					num = arr[i]
		result += arr.index(num)
		return result


class Solution:

	def minMoves(self, arr, n):
		ma = n
		count = 0
		for i in range(n - 1, -1, -1):
			if arr[i] == ma:
				count += 1
				ma -= 1
		return n - count


class Solution:

	def minMoves(self, arr, n):
		cur = n
		cou = 0
		for i in range(n - 1, -1, -1):
			if arr[i] == cur:
				cou += 1
				cur -= 1
		return n - cou


class Solution:

	def minMoves(self, arr, n):
		i = n - 1
		a = n
		while i >= 0:
			if arr[i] == a:
				a -= 1
			i -= 1
		return a


class Solution:

	def minMoves(self, arr, n):
		count = 0
		current = n
		for i in range(n - 1, -1, -1):
			if arr[i] != current:
				count += 1
			else:
				current -= 1
		return count


class Solution:

	def minMoves(self, arr, n):
		c = 0
		k = n
		for i in range(n - 1, -1, -1):
			if arr[i] == k:
				c += 1
				k -= 1
			else:
				continue
		return n - c


class Solution:

	def minMoves(self, arr, n):
		value = n
		count = 0
		for i in arr[::-1]:
			if i == value:
				count += 1
				value -= 1
		return n - count


from heapq import *

class Solution:

	def minMoves(self, arr, n):
		count = len(arr)
		max_heap = [-a for a in arr]
		heapify(max_heap)
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] == -max_heap[0]:
				heappop(max_heap)
				count -= 1
		return count


class Solution:

	def minMoves(self, arr, n):
		count = len(arr)
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] == count:
				count -= 1
		return count


class Solution:

	def minMoves(self, arr, n):
		e = n
		for ele in reversed(arr):
			if ele == e:
				e -= 1
		return e


class Solution:

	def minMoves(self, arr, n):
		count = n
		i = n - 1
		while i >= 0:
			if arr[i] == count:
				count -= 1
			i -= 1
		return count
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	print(ob.minMoves(a, n))


class Solution:

	def minMoves(self, arr, n):
		pos = dict(zip(arr, range(n)))
		p = pos[n]
		q = -1
		ans = 0
		for x in reversed(range(1, n)):
			if pos[x] > pos[x + 1]:
				p = pos[x] = q
				q -= 1
				ans += 1
		return ans


class Solution:

	def minMoves(self, s, n):
		expected = n
		for i in range(n - 1, -1, -1):
			if s[i] == expected:
				expected = expected - 1
		return expected