You are given an array A of N integers. You must perform some (possibly zero) operations to make the elements of A distinct.

In one operation, you can either:
Remove one element from the beginning of the array A and append any positive integer to the end.
Or remove one element from the end of the array A and prepend any positive integer to the beginning.

Find the minimum number of operations required to make all the elements of the array distinct.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

------ Output Format ------ 

For each test case, output the minimum number of operations required to make all the elements distinct.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 2 \cdot 10^{5}$
- The sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
3
8
1 3 3 5 1 2 4 1
4
1 2 3 4
5
10 20 10 20 30

----- Sample Output 1 ------ 
4
0
2

----- explanation 1 ------ 
Test case $1$:
Initially $A = [1, 3, 3, 5, 1, 2, 4, 1]$. Consider the following sequence of operations.
- $[1, 3, 3, 5, 1, 2, 4, \underline{1}] \xrightarrow[\mathrm{prepend} \, 6]{\mathrm{remove} \, 1} [\boldsymbol 6, 1, 3, 3, 5, 1, 2, 4]$

- $[\underline{6}, 1, 3, 3, 5, 1, 2, 4] \xrightarrow[\mathrm{append} \, 7]{\mathrm{remove} \, 6} [1, 3, 3, 5, 1, 2, 4, \boldsymbol 7]$

- $[\underline{1}, 3, 3, 5, 1, 2, 4, 7] \xrightarrow[\mathrm{append} \, 8]{\mathrm{remove} \, 1} [3, 3, 5, 1, 2, 4, 7, \boldsymbol 8]$

- $[\underline{3}, 3, 5, 1, 2, 4, 7, 8] \xrightarrow[\mathrm{append} \, 9]{\mathrm{remove} \, 3} [3, 5, 1, 2, 4, 7, 8, \boldsymbol 9]$

All the elements of $A$ are now distinct. It can be shown that it is not possible in less than $4$ operations.

Test case $2$: No operations are required since all the elements of $A$ are already distinct.

Difficulty: MEDIUM_HARD
Tags: Complete search

Amortized analysis

Constructive algorithms
Skill types: Amortized analysis

Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	A = [int(i) for i in input().split()]
	dict = {}
	ans = 4 * N
	front = 0
	back = 0
	while back < N:
		if A[back] in dict:
			for i in range(front, dict[A[back]]):
				if A[i] in dict:
					del dict[A[i]]
			ans = min(2 * min(front, N - back) + max(front, N - back), ans)
			front = dict[A[back]] + 1
			dict[A[back]] = back
			back += 1
		else:
			dict[A[back]] = back
			back += 1
	ans = min(2 * min(front, N - back) + max(front, N - back), ans)
	print(ans)


from sys import stdin
input = stdin.readline
from math import ceil, floor, sqrt, log2
from heapq import heappush, heappop
from collections import deque
from functools import lru_cache
from bisect import bisect_left, bisect_right

def rl(t=int):
	return list(map(t, input().split()))
T = int(input())
for t in range(1, T + 1):
	n = int(input())
	a = rl()
	ret = n - 1
	i = 0
	seen = set()
	for (j, cur) in enumerate(a):
		while cur in seen:
			seen.remove(a[i])
			i += 1
		seen.add(a[j])
		left = i
		right = n - j - 1
		ret = min(ret, max(left, right) + 2 * min(left, right))
	print(ret)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = n
	start = 0
	x = 0
	d = {arr[0]: 1}
	for i in range(1, n):
		d[arr[i]] = d.get(arr[i], 0) + 1
		if d[arr[i]] > 1:
			x = start
			y = n - i
			temp1 = 2 * x + y
			temp2 = 2 * y + x
			ans = min(ans, temp1, temp2)
		while d[arr[i]] > 1:
			d[arr[start]] -= 1
			start += 1
	x = start
	y = 0
	temp1 = 2 * x + y
	temp2 = 2 * y + x
	ans = min(ans, temp1, temp2)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mp = {}
	j = 0
	ans = 10000000000
	for i in range(0, n):
		if a[i] in mp:
			mp[a[i]] += 1
		else:
			mp[a[i]] = 1
		while mp[a[i]] > 1:
			mp[a[j]] -= 1
			j += 1
		x = j
		y = n - i - 1
		ans = min(ans, 2 * x + y, x + y * 2)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	ind = 0
	swap = n
	for i in range(n):
		if a[i] in d:
			d[a[i]] += 1
		else:
			d[a[i]] = 1
		while d[a[i]] > 1:
			d[a[ind]] -= 1
			ind += 1
		swap = min(swap, ind + (n - i - 1) + min(ind, n - i - 1))
	print(swap)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1 or max(Counter(a).values()) == 1:
		print(0)
	else:
		(ans, cnt, j) = (0, {}, -1)
		for i in range(n):
			try:
				val = cnt[a[i]]
				j = i - 1
				break
			except:
				cnt[a[i]] = 1
			j = i
		ans = n - j - 1
		for i in range(1, n):
			cnt[a[i - 1]] = 0
			for k in range(j + 1, n):
				try:
					val = cnt[a[k]]
					if val == 1:
						j = k - 1
						break
					cnt[a[k]] = 1
				except:
					cnt[a[k]] = 1
				j = k
			ans = min(ans, min(2 * i + n - j - 1, i + 2 * (n - j - 1)))
			if j == n - 1:
				break
		print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = defaultdict(lambda : 0, {})
	(ans, j) = (None, 0)
	for i in range(n):
		d[l[i]] += 1
		while d[l[i]] > 1:
			d[l[j]] -= 1
			j += 1
		if ans == None:
			ans = 2 * min(j, n - i - 1) + max(j, n - i - 1)
		else:
			ans = min(ans, 2 * min(j, n - i - 1) + max(j, n - i - 1))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 10 ** 10
	mp = {}
	j = 0
	for i in range(n):
		if a[i] in mp.keys():
			mp[a[i]] += 1
		else:
			mp[a[i]] = 1
		while mp[a[i]] > 1:
			mp[a[j]] -= 1
			j += 1
		ans = min(ans, 2 * min(j, n - i - 1) + max(j, n - i - 1))
	print(ans)


T = int(input())

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

def compute_next_idx(A, N):
	next_idx = [N - 1 for i in range(N)]
	i = j = 0
	cnt = dict()
	while j < N:
		j_key = str(A[j])
		prev = cnt.get(j_key, 0)
		cnt[j_key] = prev + 1
		if prev == 1:
			while i <= j:
				next_idx[i] = j - 1
				i_key = str(A[i])
				cur = cnt[i_key]
				cnt[i_key] = cur - 1
				i += 1
				if cur == 2:
					break
		j += 1
	return next_idx
while T:
	T -= 1
	N = int(input())
	A = int_arr_input()
	next_idx = compute_next_idx(A, N)
	ret = 1000000000.0
	for i in range(N):
		j = next_idx[i]
		m1 = 2 * i + N - j - 1
		m2 = i + 2 * (N - j - 1)
		ret = min(ret, min(m1, m2))
	print(ret)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dic = {}
	sample = []
	max_l = start = 0
	for (i, key) in enumerate(a):
		if key in dic and start <= dic[key]:
			start = dic[key] + 1
		elif i - start + 1 > max_l:
			max_l = i - start + 1
			sample = [[start, i]]
		elif i - start + 1 == max_l:
			sample.append([start, i])
		dic[key] = i
	ans = 10 ** 9
	for (i, j) in sample:
		ans = min(ans, min(i, n - j - 1) * 2 + max(i, n - j - 1))
	print(ans)


t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	j = 0
	cnt = 0
	mp = {}
	ans = n - 1
	for i in range(n):
		if a[i] not in mp:
			mp[a[i]] = 1
		else:
			mp[a[i]] += 1
		while mp[a[i]] > 1:
			mp[a[j]] -= 1
			j += 1
		ans = min(ans, 2 * min(j, n - 1 - i) + max(n - 1 - i, j))
	print(ans)


ans = ''
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(l, r) = (0, 0)
	maxLen = 0
	(maxL, maxR) = (-1, -1)
	candi = []
	st = set()
	while r < n:
		while r < n and arr[r] not in st:
			st.add(arr[r])
			r += 1
		if maxLen <= r - l:
			maxLen = r - l
			maxL = l
			maxR = r - 1
			candi.append([maxLen, maxL, maxR])
		while l <= r and r < n and (arr[r] in st):
			st.remove(arr[l])
			l += 1
	res = float('inf')
	for cand in candi:
		if cand[0] == maxLen:
			res = min(res, 2 * cand[1] + (n - cand[2] - 1), cand[1] + 2 * (n - cand[2] - 1))
	ans += str(res) + '\n'
print(ans)


from collections import defaultdict
for _ in range(int(input())):
	mp = defaultdict(lambda : 0)
	ans = float('inf')
	n = int(input())
	j = 0
	l = list(map(int, input().split()))
	for i in range(n):
		mp[l[i]] += 1
		while mp[l[i]] > 1:
			mp[l[j]] -= 1
			j += 1
		ans = min(ans, 2 * min(j, n - i - 1) + max(j, n - i - 1))
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	d = {}
	j = 0
	ans = 10 ** 10
	for i in range(N):
		if A[i] in d.keys():
			d[A[i]] += 1
		else:
			d[A[i]] = 1
		while d[A[i]] > 1:
			d[A[j]] -= 1
			j += 1
		ans = min(ans, 2 * min(j, N - i - 1) + max(j, N - i - 1))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(ans, j) = (n, 0)
	index = dict()
	for i in range(n):
		if a[i] in index.keys():
			j = max(j, index[a[i]])
			index[a[i]] = i + 1
		else:
			index[a[i]] = i + 1
		ans = min(ans, 2 * min(j, n - i - 1) + max(j, n - i - 1))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	hmap = {}
	l = 0
	res = 10 ** 10
	for r in range(0, n):
		if A[r] in hmap.keys():
			hmap[A[r]] += 1
		else:
			hmap[A[r]] = 1
		while hmap[A[r]] > 1:
			hmap[A[l]] -= 1
			l += 1
		res = min(res, 2 * min(l, n - r - 1) + max(l, n - r - 1))
	print(res)


for _ in range(int(input())):
	s = int(input())
	inp = list(map(int, input().split()))
	dic = {}
	j = 0
	res = 10 ** 10
	for i in range(s):
		if inp[i] not in dic.keys():
			dic[inp[i]] = 1
		else:
			dic[inp[i]] += 1
		while dic[inp[i]] > 1:
			dic[inp[j]] -= 1
			j += 1
		res = min(res, 2 * min(j, s - i - 1) + max(j, s - i - 1))
	print(res)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a = {arr[0]}
	i = 0
	j = 1
	ans = float('inf')
	while j < n:
		if arr[j] in a:
			while arr[j] in a:
				a.remove(arr[i])
				i += 1
		a.add(arr[j])
		ans = min(ans, max(i, n - j - 1) + 2 * min(i, n - j - 1))
		j += 1
	print(ans)


def solve(n, arr):
	i = 0
	seen = set()
	maxLen = 0
	left = right = -1
	res = float('inf')
	for j in range(n):
		while arr[j] in seen:
			seen.remove(arr[i])
			i += 1
		seen.add(arr[j])
		if j - i + 1 >= maxLen:
			maxLen = j - i + 1
			left = i
			right = j
			removeLeftFirst = left * 2 + n - right - 1
			removeRightFirst = (n - right - 1) * 2 + left
			res = min(res, removeLeftFirst, removeRightFirst)
	if left == 0:
		return n - right - 1
	if right == n - 1:
		return left
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


from collections import Counter, defaultdict

class Solution:

	def __init__(self):
		pass

	def solve(self, n, p):
		start = 0
		end = -1
		maxLength = 0
		seenSet = set()
		ms = []
		me = []
		while end < n - 1:
			end += 1
			while p[end] in seenSet:
				seenSet.remove(p[start])
				start += 1
			seenSet.add(p[end])
			if maxLength < end - start + 1:
				maxLength = end - start + 1
				ms = [start]
				me = [end]
			elif maxLength == end - start + 1:
				ms.append(start)
				me.append(end)
		minOp = float('inf')
		for i in range(len(ms)):
			minOp = min(n - maxLength + min(ms[i], n - me[i] - 1), minOp)
		print(minOp)
t = int(input())
s = Solution()
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s.solve(n, arr)


def printArr(a):
	s = ''
	for i in a:
		s += str(i) + ' '
	print(s[0:-1])
import sys
sys.setrecursionlimit(10 ** 5)

def topop(l, h, n):
	x = n - h - 1
	if x < l:
		return 2 * x + l
	else:
		return 2 * l + x
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(_) for _ in input().split()]
	l = 0
	h = 0
	t = 0
	d = dict()
	for i in range(n):
		x = a[i]
		if x in d and d[x] >= t:
			y = d[x]
			if topop(l, h, n) > topop(t, y, n):
				l = t
				h = y
			if topop(l, h, n) > topop(y + 1, i, n):
				l = y + 1
				h = i
			if topop(l, h, n) > topop(y, i - 1, n):
				l = y
				h = i - 1
			if topop(l, h, n) > topop(t, i - 1, n):
				l = t
				h = i - 1
			t = y + 1
		d[x] = i
	if topop(t, n - 1, n) < topop(l, h, n):
		print(topop(t, n - 1, n))
	else:
		print(topop(l, h, n))


from collections import defaultdict, Counter

def ans(l):
	n = len(l)
	d = defaultdict(lambda : 1000000)
	a = [0] * n
	for i in range(n - 1, -1, -1):
		a[i] = d[l[i]]
		d[l[i]] = i
		if i < n - 1:
			a[i] = min(a[i + 1], a[i])
	if a[0] == 1000000:
		return 0
	ans = 1000000
	for j in range(n - 1):
		if a[j + 1] == 1000000:
			ans = min(ans, j + 1)
			break
		ans = min(ans, 2 * (j + 1) + n - a[j + 1])
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	print(min(ans(s), ans(s[::-1])))


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	(unique, maxUnique, ind, s, queue) = (0, 0, 0, set(), [])
	ans = float('inf')
	for i in range(n):
		if nums[i] not in s:
			unique += 1
		else:
			if unique >= maxUnique:
				(maxUnique, ind) = (unique, i - unique)
				ans = min(ans, 2 * min(ind, n - i) + max(ind, n - i))
			while queue[0] != nums[i]:
				s.remove(queue.pop(0))
			queue.pop(0)
			unique = len(queue) + 1
		queue.append(nums[i])
		s.add(nums[i])
	if unique >= maxUnique:
		ans = min(ans, n - unique)
	print(ans)


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
from collections import defaultdict
for _ in range(I()):
	n = I()
	arr = L()
	ans = 1000000000.0
	mp = defaultdict(int)
	r = 0
	for l in range(n):
		while r < n and (not mp[arr[r]]):
			mp[arr[r]] += 1
			r += 1
		ans = min(ans, l + 2 * (n - r))
		ans = min(ans, 2 * l + (n - r))
		mp[arr[l]] -= 1
	print(ans)


from collections import defaultdict
import sys

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		vec = input().split()
		vec = [int(i) for i in vec]
		mp = {}
		mp = defaultdict(lambda : 0, mp)
		ans = n - 1
		back = 0
		front = 0
		mp[vec[0]] += 1
		x = 0
		y = n - 1
		while front < n - 1:
			front += 1
			y -= 1
			if mp[vec[front]] == 1:
				front -= 1
				y += 1
				if front == back:
					front += 1
					y -= 1
					back += 1
					x += 1
				else:
					mp[vec[back]] -= 1
					back += 1
					x += 1
			else:
				mp[vec[front]] += 1
			ans = min(ans, min(x + 2 * y, y + 2 * x))
		print(ans)
	return 0
main()


from collections import defaultdict
t = int(input())
for test in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	ans = float('inf')
	mx = max(num)
	mp = defaultdict(int)
	j = 0
	for i in range(n):
		mp[num[i]] += 1
		while mp[num[i]] > 1:
			mp[num[j]] -= 1
			j += 1
		ans = min(ans, 2 * min(j, n - i - 1) + max(j, n - i - 1))
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mp = {}
	j = 0
	ans = float('inf')
	for i in range(n):
		mp[a[i]] = mp.get(a[i], 0) + 1
		while mp[a[i]] > 1:
			mp[a[j]] -= 1
			j += 1
		ans = min(ans, 2 * min(j, n - i - 1) + max(j, n - i - 1))
	print(ans)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	hash_map = {}
	j = 0
	ans = 10 ** 10
	for i in range(len(arr)):
		if arr[i] in hash_map.keys():
			hash_map[arr[i]] += 1
		else:
			hash_map[arr[i]] = 1
		while hash_map[arr[i]] > 1:
			hash_map[arr[j]] -= 1
			j += 1
		ans = min(ans, 2 * min(j, n - i - 1) + max(j, n - i - 1))
	print(ans)


result = []
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	mapIndex = dict()
	(st, ed) = (0, n - 1)
	res = []
	for i in range(n):
		if arr[i] not in mapIndex:
			mapIndex[arr[i]] = i
			ed = i
		else:
			ind = mapIndex[arr[i]]
			e = n - 1 - ed
			res.append(min(2 * st + e, st + 2 * e))
			st = ind + 1
			while ind >= 0 and arr[ind] in mapIndex:
				if mapIndex[arr[ind]] == ind:
					del mapIndex[arr[ind]]
				ind -= 1
			mapIndex[arr[i]] = i
	e = n - 1 - ed
	res.append(min(2 * st + e, st + 2 * e))
	result.append(str(min(res)))
print('\n'.join(result))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 99999999999999
	my_dict = {}
	j = 0
	for _ in range(N):
		if A[_] in my_dict.keys():
			my_dict[A[_]] += 1
		else:
			my_dict[A[_]] = 1
		while my_dict[A[_]] > 1:
			my_dict[A[j]] -= 1
			j += 1
		ans = min(ans, 2 * min(j, N - _ - 1) + max(j, N - _ - 1))
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	h = defaultdict(int)
	c = n
	j = 0
	for i in range(n):
		if a[i] in h:
			t = h[a[i]]
		else:
			t = 0
		j = max(t, j)
		h[a[i]] = 1 + i
		c = min(c, min(j, n - i - 1) + j + n - i - 1)
	print(c)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(a % b, a)

def solve(arr, n):
	a = {}
	(temp, ans, j) = (n - 1, n, 0)
	i = 0
	while i < n:
		temp = n - i - 1
		if arr[i] in a:
			j = max(a[arr[i]], j)
		else:
			j = max(0, j)
		a[arr[i]] = 1 + i
		ans = min(ans, min(j, temp) + j + temp)
		i += 1
	return ans

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


from collections import defaultdict

def solve(a):
	heap = defaultdict(int)
	count = n
	j = 0
	for i in range(n):
		(r, temp) = (n - i - 1, heap.get(a[i], 0))
		j = max(temp, j)
		heap[a[i]] = 1 + i
		count = min(count, min(j, r) + j + r)
	return count
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a))


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	dct = defaultdict(lambda : 0)
	nee = n + 1
	(start, end) = (0, 0)
	for j in range(n):
		if end <= j:
			dct = defaultdict(lambda : 0)
			dct[arr[j]] += 1
			start = j
			end = j
		else:
			while start != j:
				dct[arr[start]] -= 1
				start += 1
		while end < n - 1 and (not dct[arr[end + 1]]):
			dct[arr[end + 1]] += 1
			end += 1
		x = max(start, n - 1 - end)
		y = min(start, n - 1 - end)
		nee = min(x + 2 * y, nee)
	print(nee)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	j = 0
	ans = 10 ** 18
	d = dict()
	for i in range(n):
		if l[i] not in d:
			d[l[i]] = 1
		else:
			d[l[i]] += 1
		while d[l[i]] > 1:
			d[l[j]] -= 1
			j += 1
		ans = min(ans, 2 * min(j, n - i - 1) + max(j, n - i - 1))
	print(ans)


from collections import defaultdict

def largest_subarray(a, n):
	index = defaultdict(lambda : 0)
	ans = 0
	j = 0
	ind1 = 0
	ind2 = 0
	for i in range(n):
		j = max(index[a[i]], j)
		ans = max(ans, i - j + 1)
		if ans == i - j + 1:
			ind1 = i
			ind2 = j
		index[a[i]] = i + 1
		i += 1
	return [ans, ind1, ind2]
from collections import Counter
import sys
input = sys.stdin.readline
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	n1 = n
	a1 = {}
	for i in range(n):
		if a[i] not in a1:
			a1[a[i]] = 1
		else:
			a1[a[i]] += 1
	n2 = len(a1)
	if n1 == n2:
		print(0)
	else:
		ans = n - 1
		x = largest_subarray(a, n)
		ind1 = min(x[1], x[2])
		ind2 = max(x[1], x[2])
		ans1 = ind1 + 2 * (n - ind2 - 1)
		ans2 = 2 * ind1 + (n - ind2 - 1)
		ans = min(ans1, ans2)
		x = largest_subarray(a[::-1], n)
		ind1 = min(x[1], x[2])
		ind2 = max(x[1], x[2])
		ans1 = ind1 + 2 * (n - ind2 - 1)
		ans2 = 2 * ind1 + (n - ind2 - 1)
		ans = min(ans1, ans2, ans)
		print(ans)


for t in range(int(input())):
	n = int(input())
	A = [int(x) for x in input().split()]
	freq = {}
	ans = n - 1
	j = 0
	for i in range(n):
		if A[i] not in freq:
			freq[A[i]] = 1
		else:
			freq[A[i]] += 1
		while freq[A[i]] > 1:
			freq[A[j]] -= 1
			j += 1
		ans = min(ans, 2 * min(j, n - i - 1) + max(j, n - i - 1))
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	arr = [int(x) for x in input().split()]
	mp = {}
	j = 0
	ans = 10 ** 10
	for i in range(n):
		if arr[i] in mp:
			mp[arr[i]] += 1
		else:
			mp[arr[i]] = 1
		while mp[arr[i]] > 1:
			mp[arr[j]] -= 1
			j += 1
		ans = min(ans, 2 * min(j, n - i - 1) + max(j, n - i - 1))
	print(ans)
	t = t - 1


t = int(input())

def solve(ar):
	mp = {}
	n = len(ar)
	ans = float('inf')
	(i, j) = (0, 0)
	while j < n:
		if ar[j] not in mp or mp[ar[j]] == 0:
			mp[ar[j]] = 1
		elif mp[ar[j]] == 1:
			while ar[i] != ar[j]:
				mp[ar[i]] -= 1
				i += 1
			i += 1
		ans = min(ans, 2 * i + n - j - 1, 2 * (n - j - 1) + i)
		j += 1
	return ans
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	print(solve(x))


T = int(input())
for t in range(T):
	n = int(input())
	arr = [int(_) for _ in input().split()]
	freq = {}
	j = 0
	ans = pow(10, 9) + 1
	for i in range(n):
		if arr[i] not in freq:
			freq[arr[i]] = 1
		else:
			freq[arr[i]] += 1
		while freq[arr[i]] > 1:
			freq[arr[j]] -= 1
			j += 1
		ans = min(ans, max(j, n - i - 1) + 2 * min(j, n - i - 1))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	l = 0
	hm = {}
	for i in range(n):
		hm[arr[i]] = 0
	res = 1000000000.0
	for i in range(n):
		hm[arr[i]] += 1
		while hm[arr[i]] > 1:
			hm[arr[l]] -= 1
			l += 1
		res = min(res, 2 * min(l, n - i - 1) + max(l, n - i - 1))
	print(res)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	coll = {}
	for i in lis:
		if i not in coll:
			coll[i] = 0
	p1 = 0
	p2 = 0
	ans = n - 1
	(l, r) = (-1, -1)
	while p2 < n:
		if coll[lis[p2]] == 0:
			coll[lis[p2]] = 1
			p2 += 1
		else:
			while coll[lis[p2]] != 0:
				coll[lis[p1]] -= 1
				p1 += 1
			coll[lis[p2]] = 1
			p2 += 1
		le = p1 - 0
		ri = n - p2
		ans = min(ans, min(2 * le + ri, le + 2 * ri))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l1 = [int(i) for i in input().split()]
	d1 = {}
	for i in l1:
		d1[i] = -1
	j = 0
	ans = -1
	for i in range(n):
		while j < n and d1[l1[j]] == -1:
			d1[l1[j]] = 1
			j += 1
		if ans == -1:
			ans = min(i * 2 + (n - j), (n - j) * 2 + i)
		else:
			ans = min(ans, i * 2 + (n - j), (n - j) * 2 + i)
		d1[l1[i]] = -1
	print(ans)


test = int(input())
while test:
	n = int(input())
	a = [int(x) for x in input().split()]
	f = dict()
	i = j = 0
	ans = 1000000.0
	while j < n:
		if a[j] in f.keys():
			f[a[j]] += 1
		else:
			f[a[j]] = 1
		if f[a[j]] > 1:
			while a[i] != a[j]:
				f[a[i]] -= 1
				i += 1
			f[a[j]] -= 1
			i += 1
		ans = min(ans, 2 * i + n - j - 1, 2 * (n - j - 1) + i)
		j += 1
	test -= 1
	print(ans)


from collections import deque
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	longest = [1] * N
	unique = {}
	start = 0
	for i in range(N):
		if A[i] in unique and unique[A[i]] >= start:
			start = min(i, unique[A[i]] + 1)
		longest[i] = i - start + 1
		unique[A[i]] = i
	max_longest = max(longest)
	ans = N - 1
	for i in range(N):
		if longest[i] == max_longest:
			left = i - max_longest + 1
			right = N - i - 1
			ans = min(ans, min(left, right) * 2 + max(left, right))
	print(ans)


import sys
from itertools import count, islice
for s in islice(sys.stdin, 2, None, 2):
	a = s.split()
	n = len(a)
	d = {}
	r = 200000.0
	j = 0
	for (i, x) in zip(count(n - 1, -1), a):
		j = max(j, d.get(x, 0))
		d[x] = n - i
		r = min(r, i + j + min(i, j))
	print(r)


import math
from bisect import bisect_left, bisect_right
import heapq
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter

def intin():
	return int(input())

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

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def exponentiation(bas, exp, mod=1000000007):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def process(arr, n):
	ans = 1000000000.0
	(left, right) = (0, n)
	curr = 0
	unique = ddc(int)
	temp = 0
	for ele in arr:
		unique[ele] += 1
		while unique[ele] > 1:
			unique[arr[left]] -= 1
			left += 1
		right -= 1
		ans = min(ans, 2 * min(left, right) + max(left, right))
	return ans

def main():
	for _ in range(int(input())):
		n = intin()
		arr = list(mapin())
		print(process(arr, n))
main()


import sys
from itertools import islice
for s in islice(sys.stdin, 2, None, 2):
	a = s.split()
	n = len(a)
	d = {}
	r = 200000.0
	k = 0
	for (i, x) in enumerate(map(int, a), 1):
		k = min(i - d.get(x, 0), k + 1)
		d[x] = i
		r = min(r, n - k + min(i - k, n - i))
	print(r)


import sys
from itertools import islice
for s in islice(sys.stdin, 2, None, 2):
	a = s.split()
	n = len(a)
	k = 0
	r = 200000.0
	d = {}
	for (i, x) in enumerate(a):
		m = i - d.get(x, -1)
		d[x] = i
		if m <= k:
			k = m
		else:
			k += 1
		r = min(r, n - k + min(i - k + 1, n - i - 1))
	print(r)


def help(a):
	map = dict()
	n = len(a)
	res = n
	j = 0
	for i in range(n):
		r = n - i - 1
		temp = 0
		if a[i] in map:
			temp = map[a[i]]
		j = max(j, temp)
		map[a[i]] = 1 + i
		res = min(res, min(j, r) + j + r)
	return res
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(help(a))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	s = {}
	start = -1
	mx = 0
	l1 = []
	for i in range(n):
		if l[i] in s and s[l[i]] > start:
			start = s[l[i]]
			s[l[i]] = i
			if i == n - 1:
				l1.append([start + 1, i])
		else:
			l1.append([start + 1, i])
			s[l[i]] = i
	if l.count(l[0]) == n and n != 1:
		print(n - 1)
	elif l1:
		l2 = []
		for i in l1:
			a = i[0]
			b = n - i[1] - 1
			if b > a:
				(a, b) = (b, a)
			l2.append(b * 2 + a)
		print(min(l2))
	else:
		print(0)


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	j = n - 1
	new = 0
	res = Counter(arr)
	if len(res) == 1:
		print(len(arr) - 1)
		continue
	if res.most_common()[0][1] == 1:
		print(0)
		continue
	i_ans = 0
	j_ans = 0
	flag1 = 0
	flag2 = 0
	while i < j:
		if res[arr[i]] > 1:
			res[arr[i]] -= 1
			i_ans = i
			flag1 = 1
		if res[arr[j]] > 1:
			res[arr[j]] -= 1
			j_ans = j
			flag2 = 1
		i += 1
		j -= 1
	if flag1 and flag2:
		x = i_ans - 0 + 1
		y = n - j_ans
	elif flag1:
		x = i_ans - 0 + 1
		y = 0
	elif flag2:
		x = 0
		y = n - j_ans
	ans1 = 2 * min(x, y) + max(x, y)
	i = 0
	res = Counter(arr)
	ans2 = 0
	i_ans = 0
	flag = 0
	while i < n:
		if res[arr[i]] > 1:
			res[arr[i]] -= 1
			i_ans = i
			flag = 1
		i += 1
	if flag:
		ans2 = i_ans - 0 + 1
		ans1 = min(ans1, ans2)
	i = n - 1
	res = Counter(arr)
	j_ans = 0
	flag = 0
	while i > -1:
		if res[arr[i]] > 1:
			res[arr[i]] -= 1
			j_ans = i
			flag = 1
		i -= 1
	if flag:
		ans3 = n - j_ans
		ans1 = min(ans1, ans3)
	print(ans1)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	mp = {}
	r = n - 1
	res = n
	j = 0
	for i in range(n):
		r = n - i - 1
		if nums[i] in mp:
			temp = mp[nums[i]]
		else:
			temp = 0
		j = max(temp, j)
		mp[nums[i]] = i + 1
		res = min(res, min(j, r) + j + r)
	print(res)


def fun(i, j, n):
	left = i
	right = n - j - 1
	if left == right:
		return 3 * left
	elif left > right:
		return 2 * right + left
	else:
		return 2 * left + right
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	j = 0
	ans = 1000000000
	for i in range(len(a)):
		if a[i] not in d.keys():
			d[a[i]] = i
		else:
			d[a[i]] = i
			while a[j] != a[i]:
				del d[a[j]]
				j += 1
			j += 1
		ans = min(fun(j, i, n), ans)
	print(ans)


from bisect import bisect_left
from re import sub
import re
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys
import copy

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
			else:
				c += 2
		i += 1
	return c

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return len(set(l))

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def calc(s):
	ans = 0
	for ele in s:
		ans += ord(ele) - 96
	return ans

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def count(n):
	ans = 0
	while n:
		ans += n % 10
		n //= 10
	return ans

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	ans = 10 ** 5 * 2
	c = 0
	d = defaultdict(lambda : -1)
	while i < n:
		if d[l[i]] == -1:
			d[l[i]] = i
			i += 1
		else:
			k1 = min(c, n - i)
			k2 = max(c, n - i)
			ans = min(ans, 2 * k1 + k2)
			i = d[l[i]] + 1
			c = i
			d = defaultdict(lambda : -1)
	k1 = min(c, n - i)
	k2 = max(c, n - i)
	ans = min(ans, 2 * k1 + k2)
	print(ans)
for _ in range(int(input())):
	solve()


from collections import defaultdict

def largest_subarray(a, n):
	index = defaultdict(lambda : 0)
	res = 0
	j = 0
	l = n - 1
	r = 0
	ans = []
	for i in range(n):
		j = max(index[a[i]], j)
		ans.append([i - j + 1, j, i])
		index[a[i]] = i + 1
		i += 1
	return ans
for _ in range(int(input())):
	l = 1000000
	n = int(input())
	a = [int(x) for x in input().split()]
	b = []
	c = []
	b = largest_subarray(a, n)
	c = max(b)
	for i in range(len(b)):
		k = 0
		if b[i][0] == c[0]:
			k = 2 * min(b[i][1], n - 1 - b[i][2])
			k += max(b[i][1], n - 1 - b[i][2])
			l = min(l, k)
	print(l)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	b = n
	j = 0
	cout = dict()
	for i in range(n):
		a = n - i - 1
		if l1[i] in cout:
			temp = cout[l1[i]]
		else:
			temp = 0
		j = max(j, temp)
		cout[l1[i]] = 1 + i
		b = min(b, min(j, a) + j + a)
	print(b)


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().strip().split()))[:n]
	dic = {}
	r = n - 1
	ans = n
	j = 0
	for i in range(n):
		r = n - i - 1
		if ar[i] in dic:
			x = dic[ar[i]]
		else:
			x = 0
		j = max(x, j)
		dic[ar[i]] = 1 + i
		ans = min(ans, min(j, r) + j + r)
	print(ans)


def solve(abbbbbdddahajsdasasadasdsadasdas, lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll):
	asdassssssssssssssssssssssssssssssssssssssfsfas = {}
	uattassaasdadasdsavsdfadasdasdasdsadasdasdasdsa = lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll - 1
	uattasadasdasdasdsadasdasdasdsa = lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
	rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr = 0
	for iterator_of_aslaaaadasdasdasdscsdc in range(lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll):
		uattassaasdadasdsavsdfadasdasdasdsadasdasdasdsa = lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll - iterator_of_aslaaaadasdasdasdscsdc - 1
		if abbbbbdddahajsdasasadasdsadasdas[iterator_of_aslaaaadasdasdasdscsdc] not in asdassssssssssssssssssssssssssssssssssssssfsfas:
			uuuuuuuuuuuuuuuuumyjyjtyjtyyyyyyyyyyyyyyyyyyyyyyjht = 0
		else:
			uuuuuuuuuuuuuuuuumyjyjtyjtyyyyyyyyyyyyyyyyyyyyyyjht = asdassssssssssssssssssssssssssssssssssssssfsfas[abbbbbdddahajsdasasadasdsadasdas[iterator_of_aslaaaadasdasdasdscsdc]]
		rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr = max(rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr, uuuuuuuuuuuuuuuuumyjyjtyjtyyyyyyyyyyyyyyyyyyyyyyjht)
		asdassssssssssssssssssssssssssssssssssssssfsfas[abbbbbdddahajsdasasadasdsadasdas[iterator_of_aslaaaadasdasdasdscsdc]] = iterator_of_aslaaaadasdasdasdscsdc + 1
		uattasadasdasdasdsadasdasdasdsa = min(uattasadasdasdasdsadasdasdasdsa, min(rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr, uattassaasdadasdsavsdfadasdasdasdsadasdasdasdsa) + rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr + uattassaasdadasdsavsdfadasdasdasdsadasdasdasdsa)
	return uattasadasdasdasdsadasdasdasdsa
for _ in range(int(input())):
	lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll = int(input())
	abbbbbdddahajsdasasadasdsadasdas = list(map(int, input().split()))
	print(solve(abbbbbdddahajsdasasadasdsadasdas, lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll))


import sys
import math
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from heapq import *

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def dist(x1, x2, y1, y2):
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def mergeSort(arr, check=lambda a, b: a < b, reverse=False):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L, check, reverse)
		mergeSort(R, check, reverse)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if check(L[i], R[j]):
				if not reverse:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
			elif not reverse:
				arr[k] = R[j]
				j += 1
			else:
				arr[k] = L[i]
				i += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

def maxSum(arr, k):
	max_sum = 0
	max_cur = 0
	for (i, num) in enumerate(arr):
		max_cur = max(max_cur + num, num)
		if max_cur > max_sum:
			max_sum = max_cur
	return max_sum

def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, b % a)

def get_power(n, m):
	i = 1
	p = -1
	while i <= n:
		i = i * m
		p += 1
	return p

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f

def find_closest(num, ar):
	min_d = float('inf')
	for num2 in ar:
		d = abs(num2 - num)
		if d < min_d:
			min_d = d
	return min_d

def check_pal(n):
	s = str(n)
	j = len(s) - 1
	i = 0
	while j > i:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

def solve(t):
	n = readInts()
	ar = readList()
	si = 0
	ei = 0
	si2 = 0
	ei2 = 0
	mxl = 0
	seen = set()
	curs = 0
	cure = 0
	tind = {}
	for (i, num) in enumerate(ar):
		if num in tind and tind[num] >= curs:
			curl = cure - curs + 1
			if curl > mxl:
				mxl = curl
				si = curs
				ei = cure
			if curl >= mxl:
				mxl = curl
				si2 = curs
				ei2 = cure
			curs = tind[num] + 1
			tind[num] = i
			cure = i
		else:
			cure = i
			tind[num] = i
			curl = cure - curs + 1
			if curl > mxl:
				mxl = curl
				si = curs
				ei = cure
			if curl >= mxl:
				mxl = curl
				si2 = curs
				ei2 = cure
	res1 = 0
	res1 += si
	res1 += n - ei - 1
	res1 += min(si, n - ei - 1)
	res2 = 0
	res2 += si2
	res2 += n - ei2 - 1
	res2 += min(si2, n - ei2 - 1)
	print(min(res1, res2))

def main():
	t = 1
	sys.setrecursionlimit(1000)
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


from sys import stdin, stdout
from collections import defaultdict, Counter, deque, OrderedDict
import math, heapq, bisect
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	d = OrderedDict()
	ans = pow(10, 10)
	start = 0
	end = 0
	cnt = 0
	for i in range(n):
		d[a[i]] = d.get(a[i], 0) + 1
		if d[a[i]] > 1:
			sol1 = 2 * start + n - (end + 1)
			sol2 = start + 2 * (n - (end + 1))
			ans = min(ans, sol1)
			ans = min(ans, sol2)
			for key in d.copy():
				del d[key]
				cnt += 1
				if key == a[i]:
					break
			d[a[i]] = d.get(a[i], 0) + 1
			start = cnt
			end = i
		else:
			end = i
	sol1 = 2 * start + n - (end + 1)
	sol2 = start + 2 * (n - (end + 1))
	ans = min(ans, sol1)
	ans = min(ans, sol2)
	print(ans)


inf = 10 ** 6
for tcase in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	l = 0
	ans = inf
	for (i, x) in enumerate(a):
		if x in d:
			v = d[x]
			while l <= v:
				del d[a[l]]
				l += 1
		d[x] = i
		r = n - 1 - i
		nop = 2 * min(l, r) + max(l, r)
		ans = min(ans, nop)
	print(ans)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(d, ans, var) = ({}, n, 0)
	for i in range(n):
		if l[i] in d:
			t = d[l[i]]
		else:
			t = 0
		var = max(var, t)
		d[l[i]] = 1 + i
		q = min(var, n - i - 1) + var + n - i - 1
		ans = min(ans, q)
	print(ans)


def func():
	n = int(input())
	arr = list(map(int, input().split()))
	dic = {}
	i = j = 0
	ans = n
	while i < n:
		r = n - 1 - i
		present = dic.get(arr[i], 0)
		j = max(j, present)
		dic[arr[i]] = i + 1
		ans = min(min(j, r) + j + r, ans)
		i += 1
	print(ans)
tc = int(input())
while tc > 0:
	func()
	tc -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dic = {}
	for i in range(n):
		dic[arr[i]] = 0
	l = 0
	h = n - 1
	ans = n
	for i in range(n):
		temp = 0
		h = n - 1 - i
		l = max(dic[arr[i]], l)
		dic[arr[i]] = 1 + i
		ans = min(ans, min(l, h) + l + h)
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	start = maxLength = 0
	dic = {}
	leftptr = rightptr = 0
	new = []
	for (i, ch) in enumerate(arr):
		if ch in dic and start <= dic[ch]:
			start = dic[ch] + 1
		elif i - start + 1 > maxLength:
			maxLength = i - start + 1
			leftptr = start
			rightptr = i
			new = [[leftptr, rightptr]]
		elif i - start + 1 == maxLength:
			new.append([start, i])
		dic[ch] = i
	ans = +math.inf
	for (i, j) in new:
		ans = min(ans, min(i, n - 1 - j) + i + n - 1 - j)
	print(ans)


t = int(input())
while t:
	a = int(input())
	b = list(map(int, input().split(' ')))
	(s, check, index) = (len(b) - 1, 0, a)
	p = 0
	local = {}
	while p < a:
		k = s - p
		c = local[b[p]] if b[p] in local.keys() else 0
		check = max(c, check)
		local[b[p]] = p + 1
		mk = k + check + min(k, check)
		index = min(index, mk)
		p += 1
	print(index)
	t -= 1


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()
	d = {}
	j = 0
	jt = n - 1
	r = n
	for i in range(n):
		jt = n - i - 1
		if l[i] in d:
			t = d[l[i]]
		else:
			t = 0
		j = max(t, j)
		d[l[i]] = i + 1
		r = min(r, min(j, jt) + j + jt)
	print(r)


import sys
from math import inf
input = lambda : sys.stdin.readline()

def finder(L):
	const = float('inf')
	dic = {}
	c = 0
	i = 0
	j = 0
	n = len(L)
	ans = 0
	(ai, aj) = (0, 0)
	while j < n:
		if L[j] not in dic.keys():
			dic[L[j]] = 1
			c += 1
		else:
			dic[L[j]] += 1
			c -= 1
		if c == j - i + 1:
			if c >= ans:
				if j != n - 1:
					x = i + n - j - 1
				else:
					x = 0
				if i != 0:
					y = i + n - j - 1
				else:
					y = 0
				const = min(const, min(i + x, n - j - 1 + y))
				ans = c
			j += 1
		else:
			while i <= j and c < j - i + 1:
				if L[i] in dic.keys():
					dic[L[i]] -= 1
					if dic[L[i]] == 0:
						c -= 1
						dic.pop(L[i])
					elif dic[L[i]] == 1:
						c += 1
				i += 1
			if c == j - i + 1:
				if c >= ans:
					if j != n - 1:
						x = i + n - j - 1
					else:
						x = 0
					if i != 0:
						y = i + n - j - 1
					else:
						y = 0
					const = min(const, min(i + x, n - j - 1 + y))
					ans = c
			j += 1
	return const
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) == n:
		print(0)
	else:
		print(finder(a))