An array is sorted if it has no inversions

A Young Boy

You are given an array of $n$ positive integers $a_1,a_2,\ldots,a_n$.

In one operation you do the following:

Choose any integer $x$.

For all $i$ such that $a_i = x$, do $a_i := 0$ (assign $0$ to $a_i$).

Find the minimum number of operations required to sort the array in non-decreasing order.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).

The second line of each test case contains $n$ positive integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print one integer — the minimum number of operations required to sort the array in non-decreasing order.


-----Examples-----

Input
5
3
3 3 2
4
1 3 1 3
5
4 1 5 3 2
4
2 4 1 2
1
1
Output
1
2
4
3
0


-----Note-----

In the first test case, you can choose $x = 3$ for the operation, the resulting array is $[0, 0, 2]$.

In the second test case, you can choose $x = 1$ for the first operation and $x = 3$ for the second operation, the resulting array is $[0, 0, 0, 0]$.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	data = list(map(int, input().split()))[::-1]
	zero_set = set()
	min_value = 10 ** 5 + 1
	end_idx = len(data)
	flag = True
	while flag:
		for (i, num) in enumerate(data[:end_idx]):
			if num in zero_set:
				min_value = 0
			elif min_value >= num:
				min_value = num
			else:
				zero_set = zero_set.union(set(data[i:]))
				end_idx = i
				min_value = 10 ** 5 + 1
				break
		else:
			flag = False
	print(len(zero_set))


t = int(input())
ans = []
ans1 = []
for e in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.reverse()
	t = 1
	for e in range(n - 1):
		if l[e] < l[e + 1]:
			break
		else:
			t += 1
	ans1.append(str(t))
	s1 = set(l[t:])
	s2 = set(l[:t])
	s3 = s1.intersection(s2)
	if s3 == set():
		ans.append(str(len(s1)))
	else:
		m1 = max(s3)
		ans.append(str(len(set(l[l.index(m1):]))))
print('\n'.join(ans))


T = int(input())
q = []
for i in range(T):
	n = int(input())
	data = [int(i) for i in input().split()]
	q.append((n, data))

def solve(n, data):
	i = n - 1
	while i > 0 and data[i] >= data[i - 1]:
		i -= 1
	get_down = set()
	for j in range(i):
		if data[j] not in get_down:
			get_down.add(data[j])
	ii = n - 1
	while ii > 0 and data[ii] not in get_down:
		ii -= 1
	for j in range(i, ii):
		if data[j] not in get_down:
			get_down.add(data[j])
	print(len(get_down))
for (n, data) in q:
	solve(n, data)


import sys
input = sys.stdin.readline
M = int(1000000000.0) + 7

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	last = dict()
	for i in range(n):
		last[a[i]] = i
	i = n - 2
	while i >= 0:
		if a[i] > a[i + 1]:
			break
		i -= 1
	r = -1
	for j in range(i, -1, -1):
		r = max(r, last[a[j]])
	ans = set()
	for i in range(r + 1):
		ans.add(a[i])
	return len(ans)
for _ in range(int(input())):
	print(solve())


for s in [*open(0)][2::2]:
	p = 0
	t = {0}
	q = {0}
	for x in map(int, s.split()):
		x *= x not in t
		if x < p:
			t |= q
			q = {0}
		q |= {x}
		p = x
	print(len(t) - 1)


import sys
input = sys.stdin.readline
T = int(input())
v = [0] * 100001
for t in range(T):
	n = int(input())
	l = [*map(int, input().split())]
	for i in l:
		v[i] = 0
	start = n - 1
	ans = 0
	add = 0
	while start > 0 and l[start] >= l[start - 1]:
		start -= 1
	if start == 0:
		print(ans)
	else:
		for i in range(start):
			if v[l[i]] == 0:
				v[l[i]] = 1
				ans += 1
		for i in range(start, n):
			if v[l[i]] == 0:
				v[l[i]] = 1
				add += 1
			elif v[l[i]] == 1 and l[i] > l[i - 1]:
				ans += add
				add = 0
		print(ans)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	bag = set()
	empty = True
	for i in range(n - 2, -1, -1):
		if arr[i] <= arr[i + 1] and empty:
			continue
		bag.add(arr[i])
		empty = False
	for i in range(n - 1, -1, -1):
		if arr[i] in bag:
			return len(set(arr[:i + 1]))
	return 0
for _ in range(int(input())):
	print(solve())


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for _ in range(t):
	n = inp()
	l = li()
	c = -1
	for i in range(len(l) - 1):
		if l[i] > l[i + 1]:
			c = i
	if c == -1:
		print(0)
	else:
		l1 = l[:c + 1]
		k = set(l1)
		m = 0
		r = c
		for i in range(c + 1, len(l)):
			if l[i] in k and l[i] > m:
				m = l[i]
				r = i
		l2 = l[:r + 1]
		print(len(set(l2)))


import sys
import math
from collections import Counter
from collections import defaultdict

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def solve(arr):
	if arr == sorted(arr):
		return 0
	n = len(arr)
	arr.reverse()
	for i in range(len(arr) - 1):
		if arr[i + 1] > arr[i]:
			ind = i
			break
	zero = n - ind - 1
	arr.reverse()
	d = {}
	for i in range(zero):
		d[arr[i]] = 0
	ans = len(d)
	for i in range(n):
		if arr[i] in d:
			arr[i] = 0
	arr.reverse()
	c = 0
	dd = {}
	for i in arr:
		if i == 0:
			c = 1
		if c and i != 0:
			if i not in dd:
				ans += 1
				dd[i] = 0
	return ans
t = int(input())
for _ in range(t):
	n = get_ints()
	arr = get_ints()
	print(solve(arr))


import sys
input = sys.stdin.readline

def int_num():
	return int(input())

def int_list():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	n = int_num()
	a = int_list()
	idx = 0
	z = {}
	for i in range(1, n):
		if a[i] in z or a[i - 1] > a[i]:
			for j in range(idx, i):
				z[a[j]] = 0
			idx = i
	ans = len(z)
	print(ans)

def main():
	t = int_num()
	while t:
		solve()
		t -= 1
	return
main()


t = int(input())
res = []
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	i = len(arr) - 2
	seen = set()
	seen.add(arr[-1])
	while i >= 0 and arr[i] <= arr[i + 1]:
		seen.add(arr[i])
		i -= 1
	if i < 0:
		res.append(0)
	else:
		zeros = set()
		count = 0
		for j in range(i + 1):
			if arr[j] not in zeros:
				zeros.add(arr[j])
				count += 1
		j = len(arr) - 1
		while j > i:
			if arr[j] in zeros:
				break
			j -= 1
		for k in range(i + 1, j + 1):
			if arr[k] not in zeros:
				zeros.add(arr[k])
				count += 1
		res.append(count)
for val in res:
	print(val)


for _ in range(int(input())):
	n = int(input())
	p = []
	z = set()
	for i in map(int, input().split()):
		if i in z:
			i = 0
		if p and i < p[-1]:
			z.update(p)
			p.clear()
		p.append(i)
	print(len(z - {0}))


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	q = []
	w = set()
	for i in a:
		if q and (q[-1] > i or i in w):
			while q:
				w.add(q.pop())
		q.append(i)
	print(len(w))


t = int(input())

def solve(n, seq):
	for i in range(n - 1, 0, -1):
		if seq[i] < seq[i - 1]:
			xx = set(seq[:i])
			keep = seq[i:]
			max_i = -1
			for j in range(n - 1, i - 1, -1):
				if seq[j] in xx:
					max_i = j
					break
			if max_i > -1:
				for val in seq[i:max_i]:
					xx.add(val)
			return len(xx)
	return 0
for _ in range(t):
	n = int(input())
	seq = [int(x) for x in input().split(' ')]
	print(solve(n, seq))


import math
import collections
import itertools
import functools

def fun(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	if arr == sorted(arr):
		print('0')
	else:
		for i in range(n - 1, 0, -1):
			if arr[i] < arr[i - 1]:
				break
		s = set(arr[:i])
		for j in range(n - 1, i - 1, -1):
			if arr[j] in s:
				break
		for k in range(i, j):
			s.add(arr[k])
		print(len(s))
for tc in range(int(input())):
	fun(tc)


t = int(input())
O = [0] * t
for ii in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	x = 0
	while x == 0:
		x = 1
		for i in range(n - 1):
			if p[n - 1 - i] < p[n - 2 - i]:
				a = set(p[:n - 1 - i])
				if 0 in a:
					O[ii] += len(a) - 1
				else:
					O[ii] += len(a)
				for y in range(n):
					if p[y] in a and p[y] != 0:
						p[y] = 0
				x = 0
				break
for i in range(t):
	print(O[i])


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	if a == sorted(a):
		print(0)
	else:
		s = set()
		index = -1
		for i in range(n - 2, -1, -1):
			if a[i] > a[i + 1]:
				index = i
				break
		for i in range(0, index + 1):
			s.add(a[i])
		index2 = -1
		for i in range(n - 1, index, -1):
			if a[i] in s:
				index2 = i
				break
		for i in range(index + 1, index2):
			s.add(a[i])
		print(len(s))
	return None
t = int(input())
for _ in range(t):
	solve()


import sys
input = lambda : sys.stdin.readline().rstrip()

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	idx = [-1] * (n + 1)
	for i in range(n):
		idx[arr[i]] = i
	now = -1
	for i in range(n - 1, 0, -1):
		if arr[i] < arr[i - 1]:
			now = i - 1
			break
	if now == -1:
		return 0
	w = now - 1
	while w != now:
		w = now
		for i in range(w, -1, -1):
			now = max(now, idx[arr[i]])
	cnt = [0] * (n + 1)
	for i in range(now + 1):
		cnt[arr[i]] = 1
	return sum(cnt)
for __ in range(int(input())):
	print(solve())


def calculate_ops(a):
	zeros = set()
	perserveds = set()
	num_ops = 0
	for index in range(len(a) - 1):
		if a[index] in zeros:
			continue
		if a[index + 1] in zeros or a[index] > a[index + 1]:
			num_ops += 1
			zeros.add(a[index])
			for perserved in perserveds:
				if perserved != a[index]:
					num_ops += 1
					zeros.add(perserved)
			perserveds = set()
			continue
		perserveds.add(a[index])
	return num_ops
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(c) for c in input().split(' ')]
	print(calculate_ops(a))


t = int(input())
ans = [0] * t
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	isGoing = True
	herr = False
	x = set()
	f = 0
	while isGoing:
		herr = False
		ind = n - 1
		for j in range(n - 2, f - 1, -1):
			if a[j] > a[ind]:
				for u in range(f, j + 1):
					x.add(a[u])
				f = j + 1
				for u in range(0, f):
					a[u] = 0
				for u in range(f, n):
					if a[u] in x:
						a[u] = 0
						herr = True
				if herr:
					break
			ind = j
		if not herr:
			isGoing = False
	ans[i] = len(x)
	if 0 in x:
		ans[i] -= 1
for i in range(t):
	print(ans[i])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sorted(a) == a:
		print(0)
		continue
	for i in range(n - 2, -1, -1):
		if a[i] > a[i + 1]:
			break
	arr = set(a[:i + 1])
	for j in range(n - 1, i - 1, -1):
		if a[j] in arr:
			break
	for k in range(i, j):
		arr.add(a[k])
	print(len(set(arr)))


for t in range(int(input())):
	n = input()
	a = {0}
	b = {0}
	c = 0
	for i in map(int, input().split()):
		if i in b:
			i = 0
		if i < c:
			b |= a
			a = {0}
		a |= {i}
		c = i
	print(len(b) - 1)


def main():
	length = int(input())
	for _ in range(length):
		n = int(input())
		lst = list(map(int, input().split(' ')))
		mono_stack = []
		seen = set()
		for num in lst:
			if mono_stack and (mono_stack[-1] > num or num in seen):
				while mono_stack:
					seen.add(mono_stack.pop())
			mono_stack.append(num)
		print(len(seen))
main()


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if a == sorted(a):
		print(0)
	else:
		for j in range(n - 1, 0, -1):
			if a[j] < a[j - 1]:
				d = j
				break
		l = set(a[0:d])
		for k in range(n - 1, d - 1, -1):
			if a[k] in l:
				break
		for m in range(d, k):
			l.add(a[m])
		print(len(l))


t = int(input())
for _ in range(t):
	n = input()
	l = list(map(int, input().split()))
	c = -1
	for i in range(len(l) - 1):
		if l[i] > l[i + 1]:
			c = i
	if c == -1:
		print(0)
	else:
		l1 = l[:c + 1]
		k = set(l1)
		m = 0
		r = c
		for i in range(c + 1, len(l)):
			if l[i] in k and l[i] > m:
				m = l[i]
				r = i
		l2 = l[:r + 1]
		print(len(set(l2)))


for _ in [0] * int(input()):
	n = int(input())
	a = [*map(int, input().split())]
	b = set()
	k = 0
	for i in range(1, n):
		if a[i] < a[i - 1] or a[i] in b:
			for j in a[k:i]:
				b.add(j)
			k = i
	print(len(b))


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		ar = list(map(int, input().split()))
		s_ar = []
		ind = 0
		for idx in range(n - 1, 0, -1):
			if ar[idx] < ar[idx - 1]:
				s_ar = set(ar[0:idx])
				ind = idx
				break
		for idx in range(n - 1, ind, -1):
			if ar[idx] in s_ar or ar[idx] < ar[idx - 1]:
				s_ar = set(ar[0:idx])
				break
		print(len(s_ar))
main()


def exe():
	for i in range(n - 1, 0, -1):
		if lst[i] >= lst[i - 1]:
			pass
		else:
			index = i
			break
	else:
		return 0
	d = {}
	for i in lst:
		d[i] = 0
	for i in range(index):
		d[lst[i]] = 1
	for i in range(index, n):
		if d[lst[i]] == 1:
			index = i
	return len(set(lst[:index]))
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	print(exe())


xx = int(input())

def cal(n, arr):
	if n == 1:
		return 0
	ck = -1
	for i in range(n - 1, 0, -1):
		if arr[i] >= arr[i - 1]:
			continue
		else:
			ck = i
			break
	if ck == -1:
		return 0
	t = set(arr[:i])
	for i in range(n - 1, ck - 1, -1):
		if arr[i] in t:
			return len(set(arr[:i + 1]))
	return len(t)
for jj in range(xx):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	print(cal(n, arr))


import enum
test = int(input())
while test:
	n = int(input())
	a = [int(x) for x in input().split()]
	i = n - 2
	ans = 0
	while i >= 0:
		if a[i] > a[i + 1]:
			break
		i -= 1
	st = set(a[:i + 1])
	ans = len(st)
	for j in range(n - 1, i, -1):
		if a[j] in st:
			ans = len(set(a[:j + 1]))
			break
	print(ans)
	test -= 1


for _ in range(int(input())):
	n = int(input())
	e = set()
	v = set()
	otv = 0
	pred = -1
	for i in map(int, input().split()):
		if pred != -1:
			if i in e:
				i = 0
			if i < pred:
				e.update(v)
				v = set()
		v.add(i)
		pred = i
	if 0 in e:
		print(len(e) - 1)
	else:
		print(len(e))


import sys
import math
from collections import Counter

def gi():
	return list(map(int, sys.stdin.readline().strip().split()))

def gs():
	return sys.stdin.readline().strip()

def fun(a):
	rev = a[::-1]
	l = len(a)
	i = 0
	while i < l - 1:
		if rev[i] < rev[i + 1]:
			break
		i += 1
	i += 1
	seen = set()
	while i < l:
		seen.add(rev[i])
		i += 1
	i = 0
	while i < l:
		if rev[i] in seen:
			break
		i += 1
	while i < l:
		seen.add(rev[i])
		i += 1
	if 0 in seen:
		seen.remove(0)
	return len(seen)
for _ in range(int(input())):
	p = int(input())
	a = gi()
	print(fun(a))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		t = -1
		for i in range(n - 1, -1, -1):
			if i > 0 and a[i - 1] > a[i]:
				t = i - 1
				break
		if t == -1:
			print(0)
		else:
			num = len(set(a[0:t + 1]))
			k = -1
			s = set(a[0:t + 1])
			for i in range(n - 1, t, -1):
				if a[i] in s:
					k = i
					break
			if k == -1:
				print(num)
			else:
				print(len(set(a[0:k + 1])))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = a[0]
	cur_s = {0}
	pre_s = {p}
	for a_i in a:
		if a_i in cur_s:
			a_i = 0
		if p > a_i:
			cur_s |= pre_s
			pre_s = set()
		p = a_i
		pre_s.add(a_i)
	print(len(cur_s) - 1)


from collections import Counter
import string
import math
import bisect
import sys
from fractions import Fraction

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))
mod = 10 ** 9 + 7
testcases = vary(1)
for _ in range(testcases):
	n = vary(1)
	arr = array_int()
	vis = set()
	ans = 0
	curmin = arr[n - 1]
	for i in range(n - 2, -1, -1):
		if arr[i] > curmin:
			curmin = 0
			if arr[i] not in vis:
				ans += 1
				vis.add(arr[i])
			arr[i] = 0
		else:
			curmin = arr[i]
	start = -1
	for i in range(n - 1, -1, -1):
		if arr[i] != 0 and arr[i] in vis:
			start = i
			break
	for i in range(start, -1, -1):
		if arr[i] != 0 and arr[i] not in vis:
			vis.add(arr[i])
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	nulified = set()
	passed = set()
	for i in range(n - 1):
		if L[i] in nulified:
			continue
		if L[i + 1] in nulified:
			next = 0
		else:
			next = L[i + 1]
		passed.add(L[i])
		if L[i] > next:
			nulified.update(passed)
			passed.clear()
	nulified.discard(0)
	print(len(nulified))


def codeforces(arr):
	ind = 0
	sort = -1
	while ind < n - 1:
		if arr[ind] <= arr[ind + 1]:
			if sort == -1:
				sort = ind
			ind += 1
			continue
		sort = -1
		ind += 1
	if sort == -1:
		dist = {}
		for i in range(n - 1):
			dist[arr[i]] = 1
		return len(dist)
	dist = {}
	for i in range(sort):
		dist[arr[i]] = 1
	ind = sort
	while ind < n:
		try:
			dist[arr[ind]]
			for i in range(sort, ind + 1):
				dist[arr[i]] = 1
			sort = ind + 1
		except:
			pass
		ind += 1
	return len(dist)
t = int(input())
for test in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(codeforces(arr))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	cur = set()
	removed = set()
	m = 0
	for i in range(n):
		if l[i] in removed:
			t = 0
		else:
			t = l[i]
		if t >= m:
			cur.add(t)
			m = t
			continue
		else:
			removed.update(cur)
			cur = {l[i]}
			m = l[i]
	print(len(removed))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if arr[i] not in d:
			d[arr[i]] = 1
		else:
			d[arr[i]] += 1
	i = n - 1
	while i > 0:
		if arr[i] == arr[i - 1]:
			d[arr[i]] -= 1
			i -= 1
		elif d[arr[i]] == 1 and arr[i - 1] < arr[i]:
			d[arr[i]] -= 1
			i -= 1
		else:
			break
	t = set(arr[:i])
	print(len(t))


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		j = n - 1
		while ar[j] >= ar[j - 1] and j > 0:
			j -= 1
		m = {'none'}
		for l in range(j):
			if ar[l] not in m:
				m.add(ar[l])
		k = n - 1
		while ar[k] not in m and k > 0:
			k -= 1
		for l in range(j, k):
			if ar[l] not in m:
				m.add(ar[l])
		m.remove('none')
		print(len(m))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = len(a) - 1
	while l > 0 and a[l - 1] <= a[l]:
		l -= 1
	sett = set(a[:l])
	temp = l
	for i in range(len(a) - 1, l - 1, -1):
		if a[i] in sett:
			temp = i
			break
	answer = set(a[:temp])
	print(len(answer))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n == 1:
		print(0)
		continue
	idx = n - 1
	for i in range(n - 1, 0, -1):
		if a[i - 1] <= a[i]:
			idx -= 1
		else:
			break
	s = set()
	for i in range(idx):
		s.add(a[i])
	last = -1
	for i in range(idx, n):
		if a[i] in s:
			last = i
	if last == -1:
		print(len(s))
	else:
		for i in range(idx, last + 1):
			s.add(a[i])
		print(len(s))


for t in range(int(input())):
	n = int(input())
	l = [*map(int, input().split())]
	if sorted(l) == l:
		print(0)
		continue
	for i in range(n - 2, -1, -1):
		if l[i] > l[i + 1]:
			break
	a = set(l[:i + 1])
	for j in range(n - 1, i - 1, -1):
		if l[j] in a:
			break
	for k in range(i, j + 1):
		a.add(l[k])
	print(len(a))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dic = {}
	ind = n - 2
	while ind >= 0 and arr[ind + 1] >= arr[ind]:
		ind -= 1
	c = 0
	for i in range(ind, -1, -1):
		if arr[i] not in dic:
			c += 1
			dic[arr[i]] = True
	for i in range(n - 2, ind - 1, -1):
		if arr[i] not in dic and arr[i + 1] in dic:
			c += 1
			dic[arr[i]] = True
	print(c)


t = int(input())
for i in range(0, t):
	n = int(input())
	w = list(map(int, input().split()))
	st = set()
	l = 100000000
	x = -1
	for g in range(len(w) - 1, -1, -1):
		if w[g] > l:
			x = g
			for j in range(0, g + 1):
				st.add(w[j])
			break
		l = w[g]
	r = x
	for g in range(x, len(w)):
		if w[g] in st:
			r = g
	st.clear()
	for g in range(0, r + 1):
		st.add(w[g])
	print(len(st))


for _ in ' ' * int(input()):
	n = int(input())
	l = list(map(int, input().split()))
	l_ = [0] * (max(l) + 1)
	for (index, value) in enumerate(l):
		l_[value] = index
	for i in range(n - 1, 0, -1):
		if l[i] < l[i - 1]:
			s = set(l[:i])
			max_index = max([l_[j] for j in s])
			print(len(set(l[:max_index + 1])))
			break
	else:
		print(0)


for t in range(int(input())):
	n = int(input())
	l = [*map(int, input().split())]
	a = []
	b = set()
	for i in l:
		if i in b:
			i = 0
		if a and i < a[-1]:
			b.update(a)
			a.clear()
		a.append(i)
	print(len(b - {0}))


for t in range(int(input())):
	n = int(input())
	l = [0] + [*map(int, input().split())]
	a = {0}
	s = []
	for i in range(n, 0, -1):
		s.append(l[i])
		if l[i] < l[i - 1]:
			a.update(l[:i])
			break
	for i in range(len(s)):
		if s[i] in a:
			a.update(s[i:])
			break
	print(len(a) - 1)


import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, sys.stdin.readline().split()))
	curr = {arr[n - 1]: n - 1}
	last = arr[n - 1]
	res = 0
	flag = False
	for i in range(n - 2, -1, -1):
		if arr[i] > last:
			flag = True
			res = i
			for x in range(i + 1):
				if arr[x] in curr:
					res = max(res, curr[arr[x]])
			break
		elif arr[i] not in curr:
			curr[arr[i]] = i
			last = arr[i]
	if flag:
		print(len(set(arr[:res + 1])))
	else:
		print(0)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = {0}
	s = []
	for i in range(n - 1, 0, -1):
		if len(a) == 1:
			s.append(l[i])
		if l[i] < l[i - 1] or len(a) > 1:
			a.add(l[i - 1])
	c = 0
	for i in s:
		if c or i in a:
			a.add(i)
			c = 1
	print(len(a) - 1)


t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split())) + [float('inf')]
	cur_min = float('-inf')
	ans = 0
	made_zero = set()
	encounter = set()
	for num in arr:
		if num < cur_min or num in made_zero:
			made_zero |= encounter
			encounter = set()
			if num not in made_zero:
				encounter.add(num)
			cur_min = num
		else:
			encounter.add(num)
			cur_min = num
	print(len(made_zero))


for _ in range(int(input())):
	n = int(input())
	X = [int(_) for _ in input().split()][::-1]
	S = set()
	for _ in range(n - 1):
		if X[_] < X[_ + 1] or len(S) != 0:
			S.add(X[_ + 1])
	for _ in range(n):
		if X[_] in S:
			print(len(set(X[_:])))
			break
	else:
		print(0)


def solve():
	n = int(input())
	lst = list(map(int, input().split()))
	s = set([lst[0]])
	st = set([])
	ans = 0
	for i in range(1, n):
		if lst[i] in st:
			lst[i] = 0
		if lst[i] < lst[i - 1]:
			ans += len(s)
			st |= s
			s = set([])
		if lst[i] in st:
			lst[i] = 0
		if lst[i] > 0:
			s.add(lst[i])
	print(ans)
for i in range(int(input())):
	solve()


cas = int(input())
for j in range(cas):
	n = int(input())
	p = 0
	t = {0}
	q = {0}
	for x in [int(i) for i in input().split()]:
		x *= x not in t
		if x < p:
			t |= q
			q = {0}
		q |= {x}
		p = x
	print(len(t) - 1)


cas = int(input())
for j in range(cas):
	n = int(input())
	a = [0] + [int(x) for x in input().split()]
	b = list(range(n + 1))
	l = 1
	c = 0
	for i in range(2, n + 1):
		if b[a[i - 1]] > b[a[i]]:
			while l < i:
				if b[a[l]] != 0:
					c = c + 1
					b[a[l]] = 0
				l = l + 1
	print(c)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	q = []
	w = set()
	for i in a:
		if q and (q[-1] > i or i in w):
			while q:
				w.add(q.pop())
		q.append(i)
	print(len(w))
	t -= 1


for _ in [0] * int(input()):
	n = int(input())
	a = [*map(int, input().split())]
	b = set()
	c = 0
	for i in range(1, n):
		if a[i] < a[i - 1] or a[i] in b:
			for d in a[c:i]:
				b.add(d)
			c = i
	print(len(b))


import collections

def min_operations(A, n):
	d = collections.defaultdict(lambda : [])
	for (i, ele) in enumerate(A):
		d[ele].append(i)
	s = 0
	operations = 0
	for i in range(1, n):
		if A[i] < A[i - 1]:
			while s < i:
				cur = A[s]
				if cur:
					for j in d[cur]:
						A[j] = 0
					operations += 1
				s += 1
	return operations
t = int(input())
while t:
	n = int(input())
	A = [int(x) for x in input().split()]
	print(min_operations(A, n))
	t -= 1


def solve(a: list, zeroes: set=None):
	if not zeroes:
		zeroes = set()
	not_ordered = False
	for i in range(1, len(a))[::-1]:
		if a[i] < a[i - 1]:
			not_ordered = True
			break
	if not_ordered:
		zeroes.update(a[:i])
	for j in range(len(a)):
		if a[j] in zeroes:
			a[j] = 0
	for i in range(1, len(a))[::-1]:
		if a[i] < a[i - 1]:
			return solve(a, zeroes)
	return len(zeroes.difference([0]))

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		print(solve(a))
main()


for _ in range(int(input())):
	n = int(input())
	arr_list = list(map(int, input().split()))
	s = set()
	f = 0
	ans = 0
	for i in range(1, n):
		if arr_list[i] in s or arr_list[i] < arr_list[i - 1]:
			for j in arr_list[f:i]:
				s.add(j)
			f = i
	print(len(s))


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	minn = arr[-1]
	rem_arr = set()
	for i in range(n - 1, -1, -1):
		if arr[i] <= minn:
			minn = arr[i]
		else:
			minn = 0
			rem_arr.add(arr[i])
	flag = False
	for i in range(n - 1, -1, -1):
		if arr[i] in rem_arr:
			flag = True
		if flag:
			rem_arr.add(arr[i])
	print(len(rem_arr))


for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	b = set()
	c = 0
	for j in range(1, len(p)):
		if p[j] < p[j - 1] or p[j] in b:
			for k in p[c:j]:
				b.add(k)
			c = j
	print(len(b))


for _ in range(int(input())):
	x = int(input())
	t = list(map(int, input().split()))
	if sorted(t) == t:
		print(0)
		continue
	for i in range(len(t) - 2, -1, -1):
		if t[i + 1] >= t[i]:
			continue
		else:
			break
	j = i
	end = set(t[:i + 1])
	for k in range(i + 1, x):
		if t[k] in end:
			j = k
	print(len(set(t[:j + 1])))


def ss(n, l):
	if l == sorted(l):
		return 0
	i = n - 2
	x = l[-1]
	while i >= 0 and l[i] <= x:
		x = l[i]
		i -= 1
	d = {}
	for x in range(i + 1):
		if l[x] in d:
			d[l[x]] += 1
		else:
			d[l[x]] = 1
	ans = len(d)
	x = n - 1
	while x > i:
		if l[x] in d:
			break
		else:
			x -= 1
	p = {}
	for y in range(x + 1):
		if l[y] in p:
			p[l[y]] += 1
		else:
			p[l[y]] = 1
	return len(p)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(ss(n, l))


import sys
input = sys.stdin.readline
t = int(input())
for t_item in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = []
	b = dict()
	res = 0
	flag = False
	ind = -1
	for i in range(n - 1, -1, -1):
		x = a[i]
		if x not in b:
			b[x] = i
		if not s or x <= s[-1][0]:
			s.append([x, i])
			continue
		else:
			s.append([x, i])
			ind = i
			flag = True
			break
	t = set()
	if flag:
		for i in range(ind, -1, -1):
			x = a[i]
			if x not in b:
				if x not in t:
					t.add(x)
					res += 1
			else:
				furthest = b[x]
				while s and s[-1][1] <= furthest:
					(q, w) = s.pop()
					furthest = max(furthest, w)
					if q not in t:
						t.add(q)
						res += 1
	print(res)


import math

def resolve(nums):
	res = 0
	stack = []
	ever_been_set = set()
	for item in nums:
		if item in ever_been_set:
			item = 0
		if len(stack) == 0:
			if item > 0:
				stack.append(item)
		elif item < stack[-1]:
			while stack:
				poped = stack.pop()
				if poped not in ever_been_set:
					ever_been_set.add(poped)
					res += 1
			if item > 0:
				stack.append(item)
		else:
			stack.append(item)
	return res

def read_input():
	n = int(input())
	nums = []
	line_1 = input().split(' ')
	for item in line_1:
		nums.append(int(item))
	return nums
case_num = int(input())
if not case_num == 0:
	for index in range(case_num):
		nums = read_input()
		res = resolve(nums)
		print(res)


case = int(input())
for i in range(case):
	n = int(input())
	a = [int(v) for v in input().split()]
	if n == 1:
		print(0)
	elif n == 2:
		if a[1] < a[0]:
			print(1)
		else:
			print(0)
	else:
		index1 = 0
		proceed = 0
		for j in range(n):
			if a[n - j - 2] > a[n - j - 1]:
				index1 = n - j - 1
				break
		b = set(a[:index1])
		while proceed == 0:
			for k in range(n):
				if n - k - 1 <= index1:
					proceed = 1
					break
				elif a[n - k - 1] in b:
					index1 = n - k - 1
					break
			b = set(a[:index1])
		print(len(b))


from collections import Counter
t = int(input())
while t > 0:
	n = int(input())
	array = list(map(int, input().split(' ')[:n]))
	if n == 1:
		print(0)
	else:
		find = -1
		for i in range(n - 1, 0, -1):
			if array[i] < array[i - 1]:
				find = i - 1
				break
		if find != -1:
			target = -1
			d = Counter(array[:find + 1])
			for i in range(n - 1, -1, -1):
				if array[i] in d:
					target = i
					break
			d1 = Counter(array[:target + 1])
			print(len(d1))
		else:
			print(0)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	visited = set()
	count = 0
	p = 0
	for i in range(n - 1):
		if a[i] not in visited:
			if a[i + 1] in visited:
				if a[i] > 0:
					visited.add(a[i])
					count += 1
					for j in range(p, i):
						if a[j] not in visited:
							visited.add(a[j])
							count += 1
					p = i + 1
			elif a[i] > a[i + 1]:
				visited.add(a[i])
				count += 1
				for j in range(p, i):
					if a[j] not in visited:
						visited.add(a[j])
						count += 1
				p = i + 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	set1 = set()
	set1.add(a[0])
	s = 0
	for i in range(1, n):
		if a[i] in set1 and a[i] != a[i - 1] or a[i] < a[i - 1]:
			s = len(set1)
		set1.add(a[i])
	print(s)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = -1
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			k = i
	d = {}
	j = 0
	for i in range(k + 1):
		d[a[i]] = 1
	for i in range(k + 1, n):
		if a[i] in d.keys():
			while j < i:
				d[a[j]] = 1
				j += 1
	c = 0
	for i in d.keys():
		c += 1
	print(c)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	st = dict()
	ans = 0
	for i in range(n - 1, -1, -1):
		if i < n - 1 and a[i] > a[i + 1]:
			ans = i
			j = 0
			while j <= ans:
				if a[j] in st:
					ans = max(ans, st[a[j]])
				j += 1
			ans = len(set(a[:ans + 1]))
			break
		if not a[i] in st:
			st[a[i]] = i
	print(ans)


ts = int(input())
for _ in range(ts):
	n = int(input())
	arr = [int(i) for i in input().split()]
	a = set()
	b = [arr[0]]
	for x in range(1, n, 1):
		if arr[x] < arr[x - 1] or (arr[x] in a and (not arr[x - 1] in a)):
			a.update(b)
			b = [arr[x]]
		else:
			b.append(arr[x])
	print(len(a))


for _ in range(int(input())):
	leng = int(input())
	num = [int(x) for x in input().split()]
	se2 = set()
	se = set()
	for i in range(1, leng):
		num1 = num[i - 1]
		num2 = num[i]
		se2.add(num1)
		if not (num1 <= num2 and num2 not in se):
			se.update(se2)
			se2 = set()
	print(len(se))


T = int(input())
while T:
	T -= 1
	L = int(input())
	arr = list(map(int, input().split()))
	j = L - 1
	ma = float('inf')
	se = {}
	while j >= 0:
		if arr[j] <= ma:
			ma = arr[j]
			se[arr[j]] = j
		else:
			break
		j -= 1
	delete = set()
	ans = 0
	if j >= 0:
		i = 0
		while i <= j:
			if arr[i] not in delete:
				ans += 1
				delete.add(arr[i])
				if arr[i] in se.keys():
					j = max(se[arr[i]], j)
			i += 1
	print(ans)


def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = inp()
for i in range(t):
	n = inp()
	arr = inlt()
	nums = set()
	processed = []
	current = 0
	last = 0
	for i in range(n):
		if arr[i] >= current and arr[i] not in nums:
			processed.append(arr[i])
			current = arr[i]
		else:
			for j in processed:
				if j in nums:
					continue
				else:
					nums.add(j)
			last = i
			if arr[i] not in nums:
				processed = [arr[i]]
				current = arr[i]
			else:
				processed = []
				current = 0
	print(len(nums))


def solve():
	n = int(input())
	for _ in range(n):
		x = int(input())
		arr = list(map(int, input().split()))
		indices = {}
		for i in range(len(arr)):
			v = arr[i]
			if v not in indices:
				indices[v] = [i]
			else:
				indices[v].append(i)
		for j in range(len(arr) - 1, -1, -1):
			if j == 0:
				print(0)
				break
			if arr[j] < arr[j - 1]:
				print(len(set(arr[0:indices[arr[j]][-1]])))
				break
			if len(indices[arr[j]]) > 1 and indices[arr[j]][-1] != indices[arr[j]][-2] + 1:
				print(len(set(arr[0:indices[arr[j]][-1] + 1])))
				break
			indices[arr[j]].pop()
solve()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	r = 0
	for i in range(n - 1, 0, -1):
		if a[i] < a[i - 1]:
			r = i
			break
	s = set()
	for i in range(r):
		s.add(a[i])
	ans = len(s)
	for i in range(n):
		if a[i] in s:
			a[i] = 0
	flag = False
	r1 = r - 1
	for i in range(n - 1, r - 1, -1):
		if i > r and a[i] == 0:
			flag = True
		if flag and a[i] > 0:
			r1 = i
			break
	if flag:
		append = set()
		for i in range(r1, r - 1, -1):
			if a[i] > 0:
				append.add(a[i])
		ans += len(append)
	print(ans)