Chef loves sorting! Chef recently learnt about a new form of sorting, endsort! 

While performing endsort of an array $A$ of $N$ distinct elements, Chef can move any element to the end of the array. 

However, Chef fears that this will take too much time. Help Chef find the number of moves to sort the given array in ascending order using endsort!

------ Input: ------

The first line contains a single integer $T$, the number of test cases. 
The first line of each test case contains a single integer $N$, the number of elements of given array $A$. 
The next line would contain $N$ space separated integers, the elements of the array. 

------ Output: ------

Print a single integer, the minimum number of moves to sort the array in ascending order using endsort.

------ Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 100000$
$1 ≤ A_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
2
5
1 2 3 4 5
5
1 3 2 5 4
----- Sample Output 1 ------ 
0
3
----- explanation 1 ------ 
For the second sample, in the first move, we move 3 to the end of the array. In the second move, we move 4 to the end and finally in the third move, we move 5 to the end.

Difficulty: HARD
Tags: Sorting

Constructive algorithms

Data structures

Ad-hoc
Skill types: Sorting

Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = [i for i in l]
	c.sort()
	j = 0
	n = len(l)
	for i in range(len(l)):
		if l[i] == c[j]:
			j += 1
	print(n - j)


for _ in range(int(input())):
	n = int(input())
	x = [int(i) for i in input().split()]
	cc = [xx for xx in x]
	cc.sort()
	move = 0
	j = 0
	for i in range(n):
		if cc[j] == x[i]:
			move += 1
			j += 1
	print(n - j)


t = int(input())
ans = []
while t:
	t = t - 1
	n = int(input())
	arr = list(map(int, input().split()))
	mi = min(arr)
	sarr = sorted(arr)
	moves = 0
	(i, j) = (arr.index(mi), 0)
	for i in range(arr.index(mi), n):
		j += sarr[j] == arr[i]
	ans.append(n - j)
for x in ans:
	print(x, end='\n')


from collections import Counter, defaultdict
import math

def solve():
	t = int(input())
	while t:
		t -= 1
		N = int(input())
		nums = [*map(int, input().split())]
		ans = sorted(nums[:])
		i = 0
		for num in nums:
			if num == ans[i]:
				i += 1
		print(N - i)
solve()


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	c = 0
	p = 0
	l = sorted(s)
	for j in range(n):
		if s[j] == l[p]:
			c += 1
			p += 1
	print(n - c)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	xd = sorted(x)
	j = ans = 0
	for i in range(n):
		if x[i] == xd[j]:
			j += 1
		else:
			ans += 1
	print(ans)


import sys

def handle(a):
	b = [(i, v) for (i, v) in enumerate(a)]
	b.sort(key=lambda p: p[1])
	cnt = 1
	l = len(b)
	for i in range(1, l):
		if b[i][0] > b[i - 1][0]:
			cnt += 1
		else:
			break
	return l - cnt
tline = sys.stdin.readline()
t = int(tline.strip())
for i in range(t):
	_line = sys.stdin.readline()
	line = sys.stdin.readline()
	a = list(map(int, line.strip().split()))
	print(handle(a))


def number_of_sorting(n, arr):
	c = 0
	p = 0
	l = sorted(arr)
	for i in range(n):
		if arr[i] == l[p]:
			c = c + 1
			p = p + 1
	return n - c
T = int(input())
for i in range(T):
	N = int(input())
	arr = [int(x) for x in input().split()]
	print(number_of_sorting(N, arr))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sorted_a = sorted(a)
	count = 0
	j = 0
	for i in range(n):
		if a[i] == sorted_a[j]:
			count += 1
			j += 1
	print(n - count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = j = 0
	sorted_arr = sorted(arr)
	for i in range(n):
		if arr[i] == sorted_arr[j]:
			cnt += 1
			j += 1
	print(n - cnt)


import math

def fn(l, n):
	s = sorted(l)
	c = 0
	j = 0
	for i in range(n):
		if l[i] == s[j]:
			j += 1
			c += 1
	return n - c
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = fn(l, n)
	print(x)


cases = int(input())
for v in range(cases):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	b = sorted(arr)
	j = 0
	cnt = 0
	for i in range(n):
		if arr[i] == b[j]:
			j += 1
			cnt += 1
	print(n - cnt)


for g in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = []
	for i in l:
		c.append(i)
	c.sort()
	count = 0
	p = 0
	for j in range(len(l)):
		if l[j] != c[p]:
			count += 1
		else:
			p += 1
	print(count)


import sys
import math
import heapq

def main(arr):
	arr_cop = arr.copy()
	heapq.heapify(arr)
	inversions = 0
	for e in arr_cop:
		if e == arr[0]:
			heapq.heappop(arr)
		else:
			inversions += 1
	print(inversions)
	return
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	main(arr)


for t in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	l = sorted(arr)
	i = 0
	j = 0
	while i < n and j < n:
		if l[i] == arr[j]:
			i += 1
			j += 1
		else:
			j += 1
	print(n - i)


for se in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	l = sorted(arr)
	i = j = 0
	while i < n and j < n:
		if l[i] == arr[j]:
			(i, j) = (i + 1, j + 1)
		else:
			j = j + 1
	print(n - i)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	l = list(arr)
	l.sort()
	i = j = 0
	while i < n and j < n:
		if l[i] == arr[j]:
			i = i + 1
			j = j + 1
		else:
			j = j + 1
	mov = n - i
	print(mov)


testcase = int(input())
for z in range(testcase):
	num = int(input())
	arr = [int(d) for d in input().split()]
	brr = sorted(arr)
	j = 0
	for i in range(num):
		if arr[i] == brr[j]:
			j = j + 1
	print(num - j)


t = int(input())
while t > 0:
	m = int(input())
	n = [int(x) for x in input().split()]
	c = n.copy()
	c.sort()
	j = 0
	for i in n:
		if i == c[j]:
			j += 1
	print(m - j)
	t -= 1


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	m = max(arr)
	minr = arr[-1]
	for i in range(n - 1, 0, -1):
		minr = min(minr, arr[i])
		if arr[i - 1] > minr:
			m = min(m, arr[i - 1])
	if m == max(arr) and arr[-1] == m:
		moves = 0
	else:
		arr.sort()
		moves = n - arr.index(m)
	print(moves)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sorted(l)
	j = 0
	for i in range(n):
		if l[i] == s[j]:
			j += 1
	print(n - j)


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		c = 0
		l = list(map(int, input().split()))
		l1 = sorted(l)
		for j in range(n):
			if l[j] == l1[c]:
				c += 1
		print(n - c)
except:
	pass


try:
	T = int(input())
	for i in range(0, T):
		N = int(input())
		p = []
		count = 0
		l = list(map(int, input().split()))
		l1 = sorted(l)
		for i in range(0, N):
			if l[i] == l1[count]:
				count = count + 1
		print(N - count)
except:
	pass


for j in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = l.copy()
	c.sort()
	count = 0
	for i in range(n):
		if l[i] == c[count]:
			count += 1
	print(n - count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	flag = False
	ctr = 0
	for i in range(n):
		if b[ctr] == a[i]:
			ctr += 1
	print(n - ctr)


for _ in range(int(input())):
	n = int(input())
	arr = [int(a) for a in input().split()]
	final = sorted(arr)
	count = 0
	for i in range(n):
		if arr[i] == final[count]:
			count += 1
	print(n - count)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	sort = sorted(arr)
	c = 0
	for j in range(n):
		if sort[c] == arr[j]:
			c += 1
	print(n - c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sorted(a)
	correct = 0
	for i in range(n):
		if s[correct] == a[i]:
			correct += 1
	print(n - correct)


for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	l = sorted(a)
	for i in range(n):
		if a[i] == l[c]:
			c += 1
	print(n - c)


for T in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	lis1 = sorted(lis)
	moves = 0
	for K in range(n):
		if lis[K] == lis1[moves]:
			moves += 1
	print(n - moves)


t = int(input())
for _ in range(t):
	a = []
	n = int(input())
	i = 0
	for x in input().split():
		a.append((int(x), i))
		i += 1
	a.sort()
	ans = 0
	ans = n - 1
	for i in range(1, n):
		if a[i][1] > a[i - 1][1]:
			ans -= 1
		else:
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	it = list(map(int, input().split()))
	s = {}
	tt = sorted(it)
	j = 1
	for i in tt:
		s[i] = j
		j += 1
	ma = n + 1
	mi = 0
	for i in it[-1::-1]:
		if s[i] > ma:
			mi = max(mi, n - s[i] + 1)
		ma = min(ma, s[i])
	print(mi)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ind = n - 1
	while ind > 0 and a[ind - 1] < a[ind]:
		ind = ind - 1
	if ind == 0:
		print(0)
	else:
		j = ind
		mini = a[j]
		value = a[j - 1]
		j -= 2
		while j >= 0:
			if a[j] < mini:
				mini = a[j]
			elif a[j] < value:
				value = a[j]
			j = j - 1
		chote = 0
		for j in range(0, n):
			if a[j] < value:
				chote += 1
		print(n - chote)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = l[:]
	b.sort()
	c = 0
	for i in range(n):
		if l[i] == b[c]:
			c += 1
	print(n - c)


t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = sorted(A)
	ctr = 0
	for i in range(len(A)):
		if A[i] == B[ctr]:
			ctr += 1
	print(n - ctr)


for T in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	(moves, B) = (0, sorted(A))
	for X in range(N):
		if A[X] == B[moves]:
			moves += 1
	print(N - moves)


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	s_num = sorted(num)
	idex = 0
	move = 0
	for i in range(n):
		if s_num[idex] == num[i]:
			idex += 1
			move += 1
	print(n - move)


t = int(input())
for _ in range(t):
	n = int(input())
	p = 0
	count = 0
	a = [int(x) for x in input().split()]
	b = sorted(a)
	for i in range(n):
		if a[i] == b[count]:
			count += 1
	print(n - count)


li = []

def fun(k):
	li.append(int(k))
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = sorted(a)
	i = 0
	j = 0
	while i < n and j < n:
		if b[i] == a[j]:
			i += 1
			j += 1
		else:
			j += 1
	k = n - i
	fun(k)
for i in range(len(li)):
	print(li[i])


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = sorted(a)
	i = 0
	j = 0
	while i < n and j < n:
		if b[i] == a[j]:
			i += 1
			j += 1
		else:
			j += 1
	k = n - i
	print(k)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(a)
	b.sort()
	i = 0
	j = 0
	while i < n and j < n:
		if b[i] == a[j]:
			i += 1
			j += 1
		else:
			j += 1
	c = n - i
	print(c)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	gi = sorted(li)
	j = 0
	c = 0
	for i in range(n):
		if gi[j] == li[i]:
			c += 1
			j += 1
	print(n - c)


T = int(input())
for t in range(T):
	n = int(input())
	A = [int(i) for i in input().split()]
	B = A[:]
	B.sort()
	ct = 0
	r = 0
	mini = max(A) + 1
	sufmin = [0] * len(A)
	sufmin[-1] = A[-1]
	for i in range(n - 2, -1, -1):
		sufmin[i] = min(sufmin[i + 1], A[i])
	for i in range(len(A) - 1):
		if A[i] > sufmin[i]:
			mini = min(mini, A[i])
	ct = 0
	for i in range(len(A)):
		if A[i] >= mini:
			ct += 1
	print(ct)


T = int(input())
for t in range(T):
	n = int(input())
	A = [int(i) for i in input().split()]
	B = A[:]
	B.sort()
	ct = 0
	r = 0
	for i in range(len(A)):
		if A[i] == B[r]:
			r += 1
	print(n - r)


for _ in range(int(input())):
	n = int(input())
	z = input().split()
	a = list(map(int, z[:n]))
	b = sorted(a) + [0]
	bx = 0
	dis = b[-2] + 1
	for ai in a:
		if ai == b[bx]:
			bx += 1
			if b[bx] == dis:
				break
		elif ai < dis:
			dis = ai
	print(n - bx)


t = int(input())
i = 0
while t > i:
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	c = x = k = 0
	flag = 0
	if a == b:
		flag = 1
	else:
		for x in range(n):
			if a[x] != b[k]:
				c += 1
			else:
				k += 1
	if flag == 1:
		print(0)
	else:
		print(c)
	i += 1


import numpy as np
nCases = int(input())
for i in range(nCases):
	n = int(input())
	arr = [int(num) for num in input().split()]
	aSort = np.argsort(arr)
	if np.all(aSort[:-1] < aSort[1:]):
		print(0)
	else:
		print(n - 1 - np.where(aSort[:-1] > aSort[1:])[0][0])


t = int(input())
while t > 0:
	t -= 1
	flag = 0
	n = int(input())
	count = 0
	a = [int(i) for i in input().strip().split(' ')]
	a_sort = sorted(a)
	index = 0
	for i in range(0, n):
		if a_sort[index] == a[i]:
			count += 1
			index += 1
	print(n - count)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = sorted(arr)
	count = 0
	for i in range(len(arr)):
		if arr[i] == arr1[count]:
			count += 1
	print(len(arr) - count)


from copy import *

def Solve(l, zz):
	c = 0
	ans = 0
	for i in range(len(l)):
		if l[i] != zz[c]:
			ans += 1
		else:
			c += 1
	print(ans)
T = int(input())
for _ in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	zz = deepcopy(l)
	zz = sorted(zz)
	Solve(l, zz)


import math
for i in range(int(input())):
	num = int(input())
	arr = [int(x) for x in input().split()]
	arr1 = sorted(arr)
	c = 0
	for i in arr:
		if arr1[c] is i:
			c += 1
	print(num - c)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * n
	for i in range(n):
		b[i] = a[i]
	b.sort()
	k = 0
	for i in range(n):
		if a[i] == b[k]:
			k += 1
	print(n - k)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	if a == b:
		print(0)
	else:
		count = 0
		k = 0
		for i in range(n):
			if a[i] != b[k]:
				count += 1
			else:
				k += 1
		print(count)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = sorted(l)
	k = 0
	count = 0
	for j in range(n):
		if l[j] == m[k]:
			k += 1
			count += 1
	print(n - count)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = list(a)
	a.sort()
	b = list(a)
	b.reverse()
	c = 0
	for i in s:
		x = a[c]
		if i == x:
			c = c + 1
	ans1 = n - c
	print(ans1)


T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	arr2 = [] + arr
	arr2.sort()
	j = 0
	q = 0
	while j < N and q < N:
		while j < N and arr[j] != arr2[q]:
			j += 1
		if j < N and arr[j] == arr2[q]:
			q += 1
	print(N - q)