Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a double-ended queue $Q$. Initially, it contains elements $Q_{1}, Q_{2}, \ldots, Q_{M}$ in this order. Each of these elements is an integer between $1$ and $N$ (inclusive) and each integer between $1$ and $N$ (inclusive) occurs in the queue at least once.

We want to pop some (possibly zero) elements from the front of the queue and some (not necessarily the same number, possibly zero) elements from the back. Among all the popped elements, each integer between $1$ and $N$ (inclusive) should appear at least once. Find the smallest possible total number of elements we need to pop.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$.
The second line contains $M$ space-separated integers $Q_{1}, Q_{2}, \ldots, Q_{M}$.

------  Output ------
For each test case, print a single line containing one integer — the minimum number of elements we need to pop.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$N ≤ M ≤ 2 \cdot 10^{5}$
for each $i$ ($1 ≤ i ≤ N$), there is at least one element equal to $i$ in the queue
the sum of $N$ over all test cases does not exceed $10^{5}$
the sum of $M$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3

2 2

1 2

2 3

1 2 1

3 6

1 1 1 3 2 2
----- Sample Output 1 ------ 
2

2

4
----- explanation 1 ------ 
Example case 1: Since $N = M$ and all elements are pairwise distinct, we have to pop everything to get each value at least once.

Example case 2: We can pop the first $2$ or the last $2$ elements.

Example case 3: We can pop the first element and the last $3$ elements, so the answer is $1 + 3 = 4$.

Difficulty: VERY_HARD
Tags: Sorting

Data structures

Complete search
Skill types: Sorting

Data structures

Complete search

Starter code:

Solutions:
def check(q, mapping, wsize):
	sum = 0
	point = 0
	for i in range(len(q)):
		if point < wsize:
			mapping[q[i]] -= 1
			point += 1
			if mapping[q[i]] == 0:
				sum -= 1
			else:
				sum += 1
		elif sum == wsize:
			return True
		else:
			mapping[q[i - wsize]] += 1
			if mapping[q[i - wsize]] == 1:
				sum += 1
			else:
				sum -= 1
			mapping[q[i]] -= 1
			if mapping[q[i]] == 0:
				sum -= 1
			else:
				sum += 1
	else:
		if sum == wsize:
			return True
		return False

def bsearch(n, m, q, mapping):
	left = n
	right = m
	ans = 0
	while left <= right:
		mid = left + (right - left) // 2
		if check(q, mapping.copy(), m - mid) == True:
			ans = mid
			right = mid - 1
		else:
			left = mid + 1
	return ans
for i in range(int(input())):
	(n, m) = map(int, input().split())
	q = [int(j) for j in input().split()]
	mapping = {j: 0 for j in range(1, n + 1)}
	for j in q:
		mapping[j] += 1
	ans = bsearch(n, m, q, mapping)
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	d = {}
	length = 0
	ans = 0
	for i in range(m):
		if l[i] not in d:
			d[l[i]] = 1
		else:
			d[l[i]] += 1
		if len(d) == n:
			length = i
			break
	q = length
	ans = length + 1
	y = m
	while q >= 0:
		d[l[q]] -= 1
		if d[l[q]] == 0:
			del d[l[q]]
		q -= 1
		while len(d) != n:
			y -= 1
			if l[y] not in d:
				d[l[y]] = 1
			else:
				d[l[y]] += 1
		ans = min(ans, q + 1 + m - y)
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	q = list(map(int, input().split()))
	sll = 0
	d = {}
	for i in range(m):
		if q[i] not in d:
			d[q[i]] = 1
		else:
			d[q[i]] += 1
		if len(d) == n:
			sll = i
			break
	y = m
	st = sll + 1
	while sll >= 0:
		d[q[sll]] -= 1
		if d[q[sll]] == 0:
			del d[q[sll]]
		sll -= 1
		while len(d) != n:
			y -= 1
			if q[y] not in d:
				d[q[y]] = 1
			else:
				d[q[y]] += 1
		st = min(st, sll + 1 + m - y)
	print(st)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	q_arr = list(map(int, input().split()))
	idx_dict = {}
	for i in range(m):
		idx_dict[q_arr[i]] = i
	idx_set = list(set(list(idx_dict.values())))
	idx_set.sort()
	new_dict = dict()
	for x in idx_set:
		new_dict[x] = 1
	ans = m - min(idx_set)
	cur = 0
	for j in range(m):
		if cur >= n:
			a = j
			break
		else:
			new_dict[idx_dict[q_arr[j]]] = -1
			a = cur
			while a < n and new_dict[idx_set[a]] == -1:
				a += 1
			if a >= n:
				break
			else:
				cur = a
				ans = min(ans, j + 1 + m - idx_set[cur])
	if j < m:
		for x in range(j, m):
			ans = min(ans, x + 1)
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	h = {}
	for i in range(m):
		h[l[i]] = i
	s = list(set(list(h.values())))
	s.sort()
	dis = dict()
	for x in s:
		dis[x] = 1
	ans = m - min(s)
	x = 0
	ln = len(s)
	for i in range(m):
		if x >= len(s):
			a = i
			break
		else:
			dis[h[l[i]]] = -1
			a = x
			while a < len(s) and dis[s[a]] == -1:
				a += 1
			if a >= len(s):
				break
			else:
				x = a
				ans = min(ans, i + 1 + m - s[x])
	if i < m:
		for x in range(i, m):
			ans = min(ans, x + 1)
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	d = defaultdict(lambda : 0)
	size = 0
	ans = []
	c = 0
	for i in range(m):
		if l[i] in d:
			d[l[i]] += 1
		else:
			d[l[i]] += 1
			size += 1
		c += 1
		if size == n:
			j = i
			break
	ans.append(c)
	for i in range(m - 1, -1, -1):
		d[l[i]] += 1
		c += 1
		if j >= 0:
			while j >= 0:
				if d[l[j]] == 1:
					break
				c -= 1
				d[l[j]] -= 1
				j -= 1
		ans.append(c)
	print(min(ans))


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	lef = defaultdict(int)
	righ = defaultdict(int)
	for i in range(m):
		righ[arr[i]] = i
	for i in range(m - 1, -1, -1):
		lef[arr[i]] = i
	ans = []
	for i in range(1, n + 1):
		ans.append(lef[i])
	ans.sort()
	operations = ans[-1] + 1
	right = m + 1
	for i in range(n - 1, -1, -1):
		val = arr[ans[i]]
		right = min(right, righ[val])
		if i == 0:
			operations = min(operations, m - right)
			continue
		operations = min(operations, ans[i - 1] + 1 + m - right)
	print(operations)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	q = list(map(int, input().split()))
	cnt = {}
	for i in range(m):
		cnt[q[i]] = cnt.get(q[i], 0) + 1
	mx = 0
	j = 0
	for i in range(m):
		cnt[q[i]] -= 1
		if cnt[q[i]] == 0:
			cnt.pop(q[i])
		while len(cnt) != n and j <= i:
			cnt[q[j]] = cnt.get(q[j], 0) + 1
			j += 1
		mx = max(mx, i - j + 1)
	print(m - mx)


def solve():
	(n, m) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	count = {}
	l = -1
	while len(count) < n:
		l = l + 1
		e = lst[l]
		if e in count:
			count[e] += 1
		else:
			count[e] = 1
	minsize = l + 1
	r = m
	while l >= 0:
		e = lst[l]
		count[e] -= 1
		if count[e] <= 0:
			count.pop(e)
		while len(count) < n:
			e = lst[r - 1]
			if e in count:
				count[e] += 1
			else:
				count[e] = 1
			r = r - 1
		l = l - 1
		minsize = min(minsize, l + 1 + (m - r))
	return minsize
t = int(input())
for _ in range(t):
	ans = solve()
	print(ans)


PI = 3.141592653589793
INF = 999999999
MOD = 1000000007

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y + MOD) % MOD

def mul(x, y):
	return x * y % MOD

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def power(x, y):
	res = 1
	x %= MOD
	while y != 0:
		if y & 1:
			res = mul(res, x)
		y >>= 1
		x = mul(x, x)
	return res

def mod_inv(n):
	return power(n, MOD - 2)

def prob(p, q):
	return mul(p, power(q, MOD - 2))

def ii():
	return int(input())

def li():
	return [int(i) for i in input().split()]

def ls():
	return [i for i in input().split()]
for t in range(ii()):
	t += 1
	(n, m) = li()
	mm = li()
	se = set()
	index = 0
	l = [-1 for i in range(n + 1)]
	store = []
	while len(se) < n:
		if l[mm[index]] == -1:
			l[mm[index]] = index
			store.append(index)
		se.add(mm[index])
		index += 1
	ans = store[-1] + 1
	ind = n - 1
	se2 = set()
	for i in range(m - 1, -1, -1):
		num = mm[i]
		se2.add(num)
		if 0 <= ind <= n - 1:
			while mm[store[ind]] in se2:
				ind -= 1
				if ind == -1:
					break
		if ind == -1:
			ans = min(ans, m - i)
		else:
			ans = min(ans, store[ind] + 1 + m - i)
	print(ans)


t = int(input())

def includes(start, end, m):
	if start < end and start == 0:
		return True
	if start < end and end == m - 1:
		return True
	elif start > end:
		return True
	return False
for _ in range(t):
	(n, m) = map(int, input().split())
	dq = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	if n == m:
		print(n)
		continue
	start = 0
	end = -1
	h = [0 for _ in range(n + 1)]
	count = 0
	res = m
	rot = 0
	while True:
		if start >= 0 and rot > 0:
			break
		while count < n:
			end += 1
			end = end % m
			e = dq[end]
			if h[e] == 0:
				count += 1
			h[e] += 1
		while count == n:
			if includes(start, end, m):
				if start < end:
					res = min(res, end - start + 1)
				elif start > end:
					res = min(res, m - start + end + 1)
			s = dq[start]
			h[s] -= 1
			if h[s] == 0:
				count -= 1
			start += 1
			if start == m:
				rot += 1
			start %= m
	h = [0 for _ in range(n + 1)]
	count = 0
	end = m
	while count < n:
		end -= 1
		e = dq[end]
		if h[e] == 0:
			count += 1
		h[e] += 1
	res = min(res, m - end)
	print(res)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	q = list(map(int, input().split()))
	if n == m:
		print(n)
	else:
		lv = [[0, 0] for i in range(n + 1)]
		rv = [[0, 0] for i in range(n + 1)]
		lc = 0
		rc = 0
		idx = m - 1
		while rc != n:
			if rv[q[idx]][0] == 0:
				rc += 1
				rv[q[idx]][0] = 1
			rv[q[idx]][1] += 1
			idx -= 1
		le = -1
		rs = idx + 1
		ans = m - rs + le + 1
		while lc != n:
			include = q[rs]
			if lv[include][0] == 0:
				le += 1
				while le < m and lv[include][0] == 0:
					if lv[q[le]][0] == 0:
						lc += 1
						lv[q[le]][0] = 1
					lv[q[le]][1] += 1
					le += 1
				le -= 1
			rv[include][0] = 0
			rv[include][1] -= 1
			if rv[include][1] == 0:
				rc -= 1
			while rs < m and (lv[q[rs]][0] == 1 or rv[q[rs]][1] > 1):
				if rv[q[rs]][0] == 1:
					rv[q[rs]][1] -= 1
					if rv[q[rs]][1] == 0:
						rc -= 1
				rs += 1
			ans = min(ans, m - rs + le + 1)
		print(ans)


def answer():
	mex = 1
	s = []
	c = [0] * (n + 1)
	for i in range(m):
		c[q[i]] += 1
		s.append(q[i])
		if q[i] == mex:
			while mex <= n and c[mex]:
				mex += 1
			if mex == n + 1:
				break
	ans = len(s)
	count = [0] * (n + 1)
	(start, took) = (m, 0)
	while len(s):
		while len(s):
			c[s[-1]] -= 1
			if c[s[-1]] == 0:
				key = s[-1]
				s.pop()
				break
			s.pop()
			ans = min(ans, len(s) + took)
		if count[key] == 0:
			for i in range(start - 1, -1, -1):
				count[q[i]] += 1
				took += 1
				if q[i] == key:
					start = i
					break
		ans = min(ans, len(s) + took)
	return ans
for T in range(int(input())):
	(n, m) = map(int, input().split())
	q = list(map(int, input().split()))
	print(answer())


from collections import Counter
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	Q = list(map(int, input().split()))
	L = Counter(Q)
	(l, r) = (0, 0)
	C = {}
	c = 0
	for i in range(m):
		q = Q[i]
		o = L[q]
		r = i + 1
		C[q] = C.get(q, 0) + 1
		if C[q] == o:
			if o == 1:
				(l, r) = (i + 1, i + 1)
				C = {}
			else:
				for j in range(l, r):
					C[Q[j]] -= 1
					if Q[j] == q:
						l = j + 1
						break
		c = max(c, r - l)
	print(m - c)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
from random import randint as ri
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	(n, m) = inp()
	arr = list(inp())
	dic = Counter()
	ct = 0
	right = 0
	pos = dd(list)
	for i in range(m):
		pos[arr[i]].append(i)
	for i in range(m - 1, -1, -1):
		ele = arr[i]
		if dic[ele] == 0:
			ct += 1
		dic[ele] += 1
		right += 1
		if ct == n:
			pt = i
			break
	ans = right
	st = pt
	left = 0
	while st < m:
		ele = arr[st]
		if dic[ele] > 1:
			dic[ele] -= 1
			right -= 1
		else:
			leftmost = pos[ele][0] + 1
			left = max(left, leftmost)
			right -= 1
		ans = min(ans, left + right)
		st += 1
	print(ans)


from collections import Counter
t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	queue = [int(i) for i in input().split()]
	count = Counter(queue)
	start = 0
	end = 0
	mx = 0
	temp_mx = 0
	while end < m and start < m and (start == end) and (count[queue[end]] == 1):
		start += 1
		end += 1
	while end < m and start < m:
		if count[queue[end]] > 1:
			count[queue[end]] -= 1
			end += 1
			temp_mx += 1
			mx = max(mx, temp_mx)
		elif count[queue[end]] == 1:
			count[queue[start]] += 1
			start += 1
			temp_mx -= 1
		else:
			break
	print(m - mx)


def solve(N, M, A):
	count = [-1] * N
	for x in A:
		count[x - 1] += 1
	nonneg = N
	ans = i = 0
	for (j, x) in enumerate(A):
		count[x - 1] -= 1
		if count[x - 1] == -1:
			nonneg -= 1
		while nonneg != N:
			count[A[i] - 1] += 1
			if count[A[i] - 1] == 0:
				nonneg += 1
			i += 1
		ans = max(ans, j - i + 1)
	return M - ans
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	print(solve(N, M, A))