You are given a sequence $a_1, a_2, \dots, a_n$, consisting of integers.

You can apply the following operation to this sequence: choose some integer $x$ and move all elements equal to $x$ either to the beginning, or to the end of $a$. Note that you have to move all these elements in one direction in one operation.

For example, if $a = [2, 1, 3, 1, 1, 3, 2]$, you can get the following sequences in one operation (for convenience, denote elements equal to $x$ as $x$-elements):   $[1, 1, 1, 2, 3, 3, 2]$ if you move all $1$-elements to the beginning;  $[2, 3, 3, 2, 1, 1, 1]$ if you move all $1$-elements to the end;  $[2, 2, 1, 3, 1, 1, 3]$ if you move all $2$-elements to the beginning;  $[1, 3, 1, 1, 3, 2, 2]$ if you move all $2$-elements to the end;  $[3, 3, 2, 1, 1, 1, 2]$ if you move all $3$-elements to the beginning;  $[2, 1, 1, 1, 2, 3, 3]$ if you move all $3$-elements to the end; 

You have to determine the minimum number of such operations so that the sequence $a$ becomes sorted in non-descending order. Non-descending order means that for all $i$ from $2$ to $n$, the condition $a_{i-1} \le a_i$ is satisfied.

Note that you have to answer $q$ independent queries.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of the queries. Each query is represented by two consecutive lines.

The first line of each query contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of elements.

The second line of each query contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le n$) — the elements.

It is guaranteed that the sum of all $n$ does not exceed $3 \cdot 10^5$.


-----Output-----

For each query print one integer — the minimum number of operation for sorting sequence $a$ in non-descending order.


-----Example-----
Input
3
7
3 1 6 6 3 1 1
8
1 1 4 4 4 7 8 8
7
4 2 5 2 6 2 7

Output
2
0
1



-----Note-----

In the first query, you can move all $1$-elements to the beginning (after that sequence turn into $[1, 1, 1, 3, 6, 6, 3]$) and then move all $6$-elements to the end.

In the second query, the sequence is sorted initially, so the answer is zero.

In the third query, you have to move all $2$-elements to the beginning.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Amortized analysis

Greedy algorithms


Solutions:
from collections import defaultdict

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		n = int(input())
		a = readIntArr()
		b = sorted(a)
		if a == b:
			allans.append(0)
			continue
		minIndexes = defaultdict(lambda : inf)
		maxIndexes = defaultdict(lambda : -inf)
		for i in range(n):
			minIndexes[a[i]] = min(minIndexes[a[i]], i)
			maxIndexes[a[i]] = max(maxIndexes[a[i]], i)
		uniqueVals = list(minIndexes.keys())
		uniqueVals.sort()
		m = len(uniqueVals)
		overlapsWithPrev = [False] * m
		overlapsWithPrev[0] = True
		for i in range(1, m):
			if minIndexes[uniqueVals[i]] < maxIndexes[uniqueVals[i - 1]]:
				overlapsWithPrev[i] = True
		mostFalsesInARow = 0
		cnts = 0
		for x in overlapsWithPrev:
			if x == False:
				cnts += 1
			else:
				mostFalsesInARow = max(mostFalsesInARow, cnts)
				cnts = 0
		mostFalsesInARow = max(mostFalsesInARow, cnts)
		ans = m - (mostFalsesInARow + 1)
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import os
import sys

def solve(arr):
	items = sorted(set(arr))
	min_max = [(float('inf'), float('-inf'))] * len(items)
	item_to_idx = {k: idx for (idx, k) in enumerate(items)}
	for (idx, a) in enumerate(arr):
		(m, M) = min_max[item_to_idx[a]]
		min_max[item_to_idx[a]] = (min(idx, m), max(idx, M))
	best = 1
	current = 1
	for i in range(1, len(items)):
		(_, prev_M) = min_max[i - 1]
		(m, _) = min_max[i]
		if prev_M <= m:
			current += 1
		else:
			current = 1
		best = max(best, current)
	return len(items) - best

def pp(input):
	T = int(input())
	for t in range(T):
		input()
		arr = list(map(int, input().strip().split()))
		print(solve(arr))
if 'paalto' in os.getcwd():
	from string_source import string_source, codeforces_parse
	pp(string_source('3\n7\n3 1 6 6 3 1 1\n8\n1 1 4 4 4 7 8 8\n7\n4 2 5 2 6 2 7'))
else:
	pp(sys.stdin.readline)


def main():
	from sys import stdin, stdout
	for _ in range(int(stdin.readline())):
		n = int(stdin.readline())
		inp1 = [-1] * (n + 1)
		inp2 = [-1] * (n + 1)
		for (i, ai) in enumerate(map(int, stdin.readline().split())):
			if inp1[ai] < 0:
				inp1[ai] = i
			inp2[ai] = i
		inp1 = tuple((inp1i for inp1i in inp1 if inp1i >= 0))
		inp2 = tuple((inp2i for inp2i in inp2 if inp2i >= 0))
		n = len(inp1)
		ans = 0
		cur = 0
		for i in range(n):
			if i and inp1[i] < inp2[i - 1]:
				cur = 1
			else:
				cur += 1
				ans = max(ans, cur)
		stdout.write(f'{n - ans}\n')
main()


import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	stored = [-1 for i in range(n + 2)]
	counted = [[0, 0] for i in range(n + 2)]
	count = 0
	for i in range(n):
		stored[a[i]] = a[i]
		if counted[a[i]][0] == 0:
			count += 1
		counted[a[i]][0] += 1
		counted[a[i]][1] += 1
	pt = n + 1
	p_pt = 0
	for i in range(n + 1, -1, -1):
		if stored[i] >= 0:
			p_pt = pt
			pt = stored[i]
			stored[i] = p_pt
		else:
			stored[i] = pt
	ans = [0 for i in range(n + 2)]
	for i in range(n):
		counted[a[i]][1] -= 1
		if counted[stored[a[i]]][0] - counted[stored[a[i]]][1] == 0 and counted[a[i]][1] == 0:
			ans[stored[a[i]]] = ans[a[i]] + 1
	maxi = max(max(ans[:n + 1]) + 1, ans[-1])
	print(count - maxi)


import os
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from io import BytesIO, IOBase
from math import gcd, inf, sqrt, ceil, floor

def lcm(a, b):
	return a * b // gcd(a, b)
MAXN = 1000004
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = Counter()
	while x != 1:
		ret[spf[x]] += 1
		x = x // spf[x]
	return ret

def printDivisors(n):
	i = 2
	z = [1, n]
	while i <= sqrt(n):
		if n % i == 0:
			if n / i == i:
				z.append(i)
			else:
				z.append(i)
				z.append(n // i)
		i = i + 1
	return z

def create(n, x, f):
	pq = len(bin(n)[2:])
	if f == 0:
		tt = min
	else:
		tt = max
	dp = [[inf] * n for _ in range(pq)]
	dp[0] = x
	for i in range(1, pq):
		for j in range(n - (1 << i) + 1):
			dp[i][j] = tt(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)])
	return dp

def enquiry(l, r, dp, f):
	if l > r:
		return inf if not f else -inf
	if f == 1:
		tt = max
	else:
		tt = min
	pq1 = len(bin(r - l + 1)[2:]) - 1
	return tt(dp[pq1][l], dp[pq1][r - (1 << pq1) + 1])

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	x = []
	for i in range(2, n + 1):
		if prime[i]:
			x.append(i)
	return x

def main():
	for _ in range(int(input())):
		n = int(input())
		a = [int(X) for X in input().split()]
		x = sorted(list(set(a)))
		y = [-1] * n
		(mi, ma) = ([-1] * len(x), [0] * len(x))
		dp = [1] * len(x)
		for i in range(len(x)):
			y[x[i] - 1] = i
		for i in range(n):
			if mi[y[a[i] - 1]] == -1:
				mi[y[a[i] - 1]] = i
			ma[y[a[i] - 1]] = i
		for i in range(1, len(x)):
			if mi[i] > ma[i - 1]:
				dp[i] += dp[i - 1]
		print(len(x) - max(dp))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import math

def read_line():
	return sys.stdin.readline()[:-1]

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

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]
t = read_int()
for i in range(t):
	n = read_int()
	a = read_int_line()
	d = {}
	for i in range(n):
		if a[i] in d:
			d[a[i]].append(i)
		else:
			d[a[i]] = [i]
	dp = [1] * len(list(d.keys()))
	s = list(d.keys())
	s.sort()
	for i in range(len(s) - 2, -1, -1):
		if d[s[i]][-1] < d[s[i + 1]][0]:
			dp[i] = dp[i + 1] + 1
		else:
			dp[i] = 1
	ans = len(s) - max(dp)
	print(ans)


import sys as _sys

def main():
	q = int(input())
	for i_q in range(q):
		(n,) = _read_ints()
		a = tuple(_read_ints())
		result = find_min_sorting_cost(sequence=a)
		print(result)

def _read_line():
	result = _sys.stdin.readline()
	assert result[-1] == '\n'
	return result[:-1]

def _read_ints():
	return map(int, _read_line().split(' '))

def find_min_sorting_cost(sequence):
	sequence = tuple(sequence)
	if not sequence:
		return 0
	indices_by_values = {x: [] for x in sequence}
	for (i, x) in enumerate(sequence):
		indices_by_values[x].append(i)
	borders_by_values = {x: (indices[0], indices[-1]) for (x, indices) in indices_by_values.items()}
	borders_sorted_by_values = [borders for (x, borders) in sorted(borders_by_values.items())]
	max_cost_can_keep_n = curr_can_keep_n = 1
	for (prev_border, curr_border) in zip(borders_sorted_by_values, borders_sorted_by_values[1:]):
		if curr_border[0] > prev_border[1]:
			curr_can_keep_n += 1
		else:
			if curr_can_keep_n > max_cost_can_keep_n:
				max_cost_can_keep_n = curr_can_keep_n
			curr_can_keep_n = 1
	if curr_can_keep_n > max_cost_can_keep_n:
		max_cost_can_keep_n = curr_can_keep_n
	return len(set(sequence)) - max_cost_can_keep_n
main()


from sys import stdin
input = stdin.readline

def main():
	anses = []
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		f = [0] * (n + 1)
		d = sorted(list(set(a)))
		for q in range(1, len(d) + 1):
			f[d[q - 1]] = q
		for q in range(len(a)):
			a[q] = f[a[q]]
		n = len(d)
		(starts, ends) = ([-1] * (n + 1), [n + 1] * (n + 1))
		for q in range(len(a)):
			if starts[a[q]] == -1:
				starts[a[q]] = q
			ends[a[q]] = q
		s = [0] * (n + 1)
		max1 = -float('inf')
		for q in range(1, n + 1):
			s[q] = s[q - 1] * (ends[q - 1] < starts[q]) + 1
			max1 = max(max1, s[q])
		anses.append(str(len(d) - max1))
	print('\n'.join(anses))
main()


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	s = sorted(list(s))
	ref = {x: i for (i, x) in enumerate(list(s))}
	sz = len(s)
	L = [1 << 32] * sz
	R = [-1 << 32] * sz
	for i in range(n):
		k = ref[a[i]]
		L[k] = min(L[k], i)
		R[k] = max(R[k], i)
	dp = [0] * sz
	for k in range(sz):
		if k == 0 or L[k] < R[k - 1]:
			dp[k] = 1
		else:
			dp[k] = 1 + dp[k - 1]
	ans = 1 << 32
	for k in range(sz):
		ans = min(ans, sz - dp[k])
	print(ans)
	return 0
for nt in range(int(input())):
	solve()


from sys import stdin
input = stdin.readline

def Input():
	global A, n, D, F
	n = int(input())
	A = list(map(int, input().split()))
	D = sorted(list(set(A)))
	F = [0] * (n + 1)

def Ans():
	for i in range(1, len(D) + 1):
		F[D[i - 1]] = i
	for i in range(n):
		A[i] = F[A[i]]
	m = len(D)
	Start = [-1] * (m + 1)
	End = [n + 1] * (m + 1)
	for i in range(n):
		if Start[A[i]] == -1:
			Start[A[i]] = i
		End[A[i]] = i
	S = [0] * (m + 1)
	Max = -float('inf')
	for i in range(1, m + 1):
		S[i] = S[i - 1] * (End[i - 1] < Start[i]) + 1
		Max = max(Max, S[i])
	Result.append(str(m - Max))

def main():
	global Result
	Result = []
	for _ in range(int(input())):
		Input()
		Ans()
	print('\n'.join(Result))
main()


import copy

def DeleteRepetitionsIn(Array):
	AlreadyRead = {}
	index = 0
	ConstantArray = copy.deepcopy(Array)
	for a in range(len(ConstantArray)):
		if Array[index] not in AlreadyRead:
			AlreadyRead[Array[index]] = ''
			index += 1
			continue
		Array = Array[0:index] + Array[index + 1:len(Array)]
	return Array

def DeleteRepetitionsIn2(Array):
	AlreadyRead = {}
	for elem in Array:
		if elem in AlreadyRead:
			continue
		AlreadyRead[elem] = ''
	return list(AlreadyRead)
Results = []
ArraysNumber = int(input())
for e in range(ArraysNumber):
	AbsolutelyUselessNumber = int(input())
	Array = list(map(int, input().split()))
	if len(Array) == 1:
		Results.append(0)
		continue
	TheRightOrder = DeleteRepetitionsIn2(Array)
	TheRightOrder.sort()
	TheCurrentOrder = {}
	for i in range(len(Array)):
		if Array[i] not in TheCurrentOrder:
			TheCurrentOrder[Array[i]] = [i, i]
			continue
		TheCurrentOrder[Array[i]][1] = i
	TheCurrentResult = 1
	TheMaxResult = 1
	for i in range(len(TheRightOrder)):
		if i == len(TheRightOrder) - 1:
			if TheCurrentResult >= TheMaxResult:
				TheMaxResult = TheCurrentResult
			continue
		if TheCurrentOrder[TheRightOrder[i]][1] > TheCurrentOrder[TheRightOrder[i + 1]][0]:
			if TheCurrentResult >= TheMaxResult:
				TheMaxResult = TheCurrentResult
			TheCurrentResult = 1
			continue
		TheCurrentResult += 1
	Results.append(len(TheRightOrder) - TheMaxResult)
for i in Results:
	print(i)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

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

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

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def ctd(chr):
	return ord(chr) - ord('a')
mod = 998244353
INF = float('inf')
from bisect import bisect_left

def main():
	for _ in range(N()):
		n = N()
		arr = RLL()
		dic = defaultdict(list)
		for i in range(n):
			dic[arr[i]].append(i)
		nl = list(dic.keys())
		nl.sort(reverse=1)
		le = len(nl)
		dp = [1] * le
		for i in range(1, le):
			if dic[nl[i]][-1] < dic[nl[i - 1]][0]:
				dp[i] = dp[i - 1] + 1
		print(le - max(dp))
main()


from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
inf = float('inf')
from functools import cmp_to_key
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

def geti():
	return map(int, input().strip().split())

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

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

def gets():
	return input().strip()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')

def solve():
	for _ in range(geta()):
		n = geta()
		a = getl()
		mini = dd(int)
		maxi = dd(int)
		for i in range(n):
			if a[i] not in mini:
				mini[a[i]] = i
			maxi[a[i]] = i
		order = sorted(set(a))
		good = 0
		count = 1
		for i in range(1, len(order)):
			if mini[order[i]] > maxi[order[i - 1]]:
				count += 1
			else:
				good = max(good, count)
				count = 1
		good = max(good, count)
		print(len(order) - good)
solve()