Martians are actively engaged in interplanetary trade. Olymp City, the Martian city known for its spaceport, has become a place where goods from all the corners of our Galaxy come. To deliver even more freight from faraway planets, Martians need fast spaceships.

A group of scientists conducts experiments to build a fast engine for the new spaceship. In the current experiment, there are $n$ elementary particles, the $i$-th of them has type $a_i$.

Denote a subsegment of the particle sequence ($a_1, a_2, \dots, a_n$) as a sequence ($a_l, a_{l+1}, \dots, a_r$) for some left bound $l$ and right bound $r$ ($1 \le l \le r \le n$). For instance, the sequence $(1\ 4\ 2\ 8\ 5\ 7)$ for $l=2$ and $r=4$ has the sequence $(4\ 2\ 8)$ as a subsegment. Two subsegments are considered different if at least one bound of those subsegments differs.

Note that the subsegments can be equal as sequences but still considered different. For example, consider the sequence $(1\ 1\ 1\ 1\ 1)$ and two of its subsegments: one with $l=1$ and $r=3$ and another with $l=2$ and $r=4$. Both subsegments are equal to $(1\ 1\ 1)$, but still considered different, as their left and right bounds differ.

The scientists want to conduct a reaction to get two different subsegments of the same length. Denote this length $k$. The resulting pair of subsegments must be harmonious, i. e. for some $i$ ($1 \le i \le k$) it must be true that the types of particles on the $i$-th position are the same for these two subsegments. For example, the pair $(1\ 7\ 3)$ and $(4\ 7\ 8)$ is harmonious, as both subsegments have $7$ on the second position. The pair $(1\ 2\ 3)$ and $(3\ 1\ 2)$ is not harmonious.

The longer are harmonious subsegments, the more chances for the scientists to design a fast engine. So, they asked you to calculate the maximal possible length of harmonious pair made of different subsegments.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases. The following are descriptions of the test cases.

The first line contains an integer $n$ ($2 \le n \le 150000$) — the amount of elementary particles in the sequence.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 150000$) — types of elementary particles.

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


-----Output-----

For each test, print a single integer, maximal possible length of harmonious pair made of different subsegments. If such pair does not exist, print $-1$ instead.


-----Examples-----

Input
4
7
3 1 5 2 1 3 4
6
1 1 1 1 1 1
6
1 4 2 8 5 7
2
15 15
Output
4
5
-1
1


-----Note-----

The first test case is shown on the picture below:

As you can see from it, you may choose the subsegments $(2\ 1\ 3\ 4)$ and $(3\ 1\ 5\ 2)$, which are a harmonious pair. Their length is equal to $4$, so the answer is $4$.

In the second test case, you need to take two subsegments: one with $l=1$ and $r=5$, and one with $l=2$ and $r=6$. It's not hard to observe that these segments are a harmonious pair and considered different even though they are both equal to $(1\ 1\ 1\ 1\ 1)$.

In the third test case, you cannot make a harmonious pair, so the answer is $-1$.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Sorting

Greedy algorithms


Solutions:
def solve(n, a):
	max_value = 1000000
	res = max_value
	inds = {}
	for (i, x) in enumerate(a):
		if x in inds:
			res = min(res, i - inds[x])
		inds[x] = i
	result = n - res if res < max_value else -1
	return result
T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in input().split()]
	result = solve(n, a)
	print(result)


import collections

def problem2(n, arr):
	hashmap = collections.defaultdict(int)
	ans = -1
	for (i, v) in enumerate(arr):
		if v in hashmap:
			ans = max(ans, n - (i - hashmap[v]))
		hashmap[v] = i
	print(ans)
for _ in range(int(input())):
	n = int(input())
	arr = [int(num) for num in input().split(' ')]
	problem2(n, arr)


def solve():
	n = int(input())
	A = [int(x) for x in input().split()]
	last = [None] * (max(A) + 1)
	res = -1
	for (i, x) in enumerate(A):
		if last[x] is not None:
			res = max(res, last[x] + n - i)
		last[x] = i
	return res
t = int(input())
for _ in range(t):
	print(solve())


def solve(n, a):
	c = [-1] * (max(a) + 1)
	ans = -1
	for i in range(n):
		if c[a[i]] >= 0:
			ans = max(ans, n - (i - c[a[i]]))
		c[a[i]] = i
	print(ans)
debugmode = 0
if debugmode:
	with open('input.txt', 'r') as f:
		t = int(f.readline())
		for _ in range(t):
			n = int(f.readline())
			a = list(map(int, f.readline().split()))
			solve(n, a)
else:
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		solve(n, a)


a = []
pre = []
for i in range(150001):
	a.append(-1)
	pre.append(-1)
for t in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	ans = -1
	for i in range(n):
		if a[c[i]] != t:
			a[c[i]] = t
		elif pre[c[i]] + n - i > ans:
			ans = pre[c[i]] + n - i
		pre[c[i]] = i
	print(ans)


from sys import exit
t = int(input())
while t:
	l = int(input())
	val = list(map(int, input('').split()))
	mindis = 150000
	dict = {}
	for (index, i) in enumerate(val):
		if dict.get(i) or dict.get(i) == 0:
			ans = index - dict.get(i)
			mindis = ans if mindis > ans else mindis
		dict[i] = index
	if mindis == 150000:
		print(-1)
	else:
		print(l - mindis)
	t -= 1


ans = []
for _ in range(int(input())):
	n = int(input())
	kol = [-1] * 150002
	x = list(map(int, input().split()))
	otv = n + 1
	for i in range(n):
		if kol[x[i]] != -1:
			otv = min(otv, i - kol[x[i]])
			kol[x[i]] = i
		else:
			kol[x[i]] = i
	if otv == n + 1:
		otv = -1
	else:
		otv = n - otv
	ans.append(otv)
print('\n'.join([str(i) for i in ans]))


import sys, bisect, math
from collections import deque, Counter
input = lambda : sys.stdin.readline().strip()
ceil = lambda x: math.ceil(x)
mod = 10 ** 9 + 7

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	m = -1
	d = {}
	for i in range(n):
		if a[i] in d:
			m = max(m, n - i + d[a[i]])
		d[a[i]] = i
	return m
t = 1
t = int(input())
for _ in range(t):
	print(solve())


t = int(input())
for i in range(0, t):
	n = int(input())
	lis = list(map(int, input().split()))
	dic = {}
	ans = 0
	for j in range(0, n):
		try:
			m = dic[lis[j]]
			s = dic[lis[j]] + n - j
			if ans < s:
				ans = s
			dic[lis[j]] = j
		except:
			dic[lis[j]] = j
	if ans == 0:
		print(-1)
	else:
		print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	arr = [-1] * (max(a) + 1)
	ans = -1
	for (i, x) in enumerate(a):
		if arr[x] != -1:
			ans = max(ans, n - i + arr[x])
		arr[x] = i
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = [-1] * (max(a) + 1)
	ans = -1
	for i in range(n):
		if c[a[i]] >= 0:
			ans = max(ans, n - (i - c[a[i]]))
		c[a[i]] = i
	print(ans)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	marker = [-1] * 150001
	ans = 150001
	for i in range(n):
		if marker[a[i]] == -1:
			marker[a[i]] = i
		else:
			ans = min(ans, i - marker[a[i]])
			marker[a[i]] = i
	if ans == 150001:
		print(-1)
	else:
		print(n - ans)


for s in [*open(0)][2::2]:
	a = s.split()
	r = i = -1
	d = {}
	for x in a:
		i += 1
		r = max(r, len(a) - i + d.get(x, -200000.0))
		d[x] = i
	print(r)


for s in [*open(0)][2::2]:
	d = {}
	i = 0
	r = 1
	for x in s.split():
		r += r > i
		r = min(r, i - d.get(x, -r))
		d[x] = i
		i += 1
	print(i - r)


a = int(input())
for x in range(a):
	b = int(input())
	d = list(map(int, input().split()))
	l = 0
	h = {}
	for y in range(b):
		if h.get(d[y]) != None:
			l = max(h[d[y]] + (b - y), l)
			h[d[y]] = y
		else:
			h[d[y]] = y
	if l == 0:
		print(-1)
	else:
		print(l)


s = int(input())
for i in range(s):
	n = int(input())
	arr = list(map(int, input().split()))
	positions = {}
	ans = -1
	for j in range(n):
		if arr[j] in positions:
			a = positions[arr[j]] - j + n
			ans = max(ans, a)
		positions[arr[j]] = j
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	last = {}
	ans = -1
	for i in range(n):
		if a[i] in last:
			ans = max(ans, last[a[i]] + n - i)
		last[a[i]] = i
	print(ans)


def getParticles():
	n = int(input())
	arr = list(map(int, input().split()))
	indexes = dict()
	for i in range(n):
		exist = indexes.get(arr[i], [])
		exist.append(i)
		indexes[arr[i]] = exist
	maxLen = -1
	for (key, value) in indexes.items():
		for i in range(1, len(value)):
			if n - value[i] + value[i - 1] > maxLen:
				maxLen = n - value[i] + value[i - 1]
			if maxLen == n - 1:
				break
	print(maxLen)
	return
t = int(input())
for i in range(t):
	getParticles()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	coord = {}
	d = {}
	for i in range(n):
		x = a[i]
		if x not in coord:
			coord[x] = i
		else:
			if x not in d:
				d[x] = i - coord[x]
			else:
				d[x] = min(d[x], i - coord[x])
			coord[x] = i
	if len(d) == 0:
		print(-1)
	else:
		print(n - min(d.values()))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = [-1] * 150000
	mn = n + 1
	for i in range(n):
		if l[a[i] - 1] != -1:
			mn = min(mn, i - l[a[i] - 1])
		l[a[i] - 1] = i
	print(n - mn)


def solve():
	n = int(input())
	arr = input().split()
	d = {}
	for i in range(n):
		if arr[i] not in d:
			d[arr[i]] = [i]
		else:
			d[arr[i]].append(i)
	ans = -1
	for i in d:
		if len(d[i]) < 2:
			continue
		for j in range(1, len(d[i])):
			first = d[i][j - 1]
			last = d[i][j]
			t = n - (last - first)
			ans = max(t, ans)
	print(ans)
for _ in range(int(input())):
	solve()


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.reverse()
	d = {}
	now = set()
	ma = -1
	for i in range(n):
		if not l[i] in now:
			now.add(l[i])
			d[l[i]] = i
		else:
			ma = max(n - i + d[l[i]], ma)
			d[l[i]] = i
	if ma == -1:
		print(-1)
	else:
		print(ma)


_ = int(input())
for _ in range(0, _):
	n = int(input())
	st = [-1] * 150010
	res = -1
	a = input().split()
	for j in range(0, len(a)):
		a[j] = int(a[j])
	for i in range(0, n):
		if st[a[i]] != -1:
			res = max(res, st[a[i]] + n - i)
		st[a[i]] = i
	print(res)


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	m = {}
	for i in range(n):
		if a[i] in m:
			m[a[i]].append(i)
		else:
			m[a[i]] = [i]
	best = -1
	for (k, v) in m.items():
		for i in range(len(v) - 1):
			(l, r) = (v[i], v[i + 1])
			best = max(best, l + (n - r - 1) + 1)
	return best
t = int(input())
for tc in range(t):
	print(solve())


def maxLen(n, arr):
	pos = {}
	for i in range(n):
		if pos.get(arr[i]):
			pos[arr[i]].append(i)
		else:
			pos[arr[i]] = [i]
	max_len = -1
	for i in pos.keys():
		if len(pos[i]) > 1:
			for j in range(1, len(pos[i])):
				max_len = max(max_len, pos[i][j - 1] + (n - pos[i][j]))
	return max_len
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(maxLen(n, arr))


import math
nt = int(input())
ans = []

def calc(indices, n):
	maxs = 0
	siz = 0
	for x in range(len(indices) - 1):
		siz = indices[x] + n - indices[x + 1]
		if siz > maxs:
			maxs = siz
	return maxs

def soln(arr, n):
	d = {}
	maxc = 0
	for x in range(n):
		if d.get(arr[x]) == None:
			d[arr[x]] = [x]
		else:
			d[arr[x]].append(x)
	p = list(d.keys())
	for x in range(len(p)):
		if len(d[p[x]]) >= 2:
			indices = d[p[x]]
			c = calc(indices, n)
			if c > maxc:
				maxc = c
	if maxc == 0:
		return -1
	else:
		return maxc
for x in range(nt):
	n = int(input())
	x = list(map(int, input().split()))
	ans.append(soln(x, n))
for a in ans:
	print(a)


T = int(input())
for testcase in range(1, T + 1):
	n = int(input())
	a = list(map(int, input().split()))
	h = {}
	for (i, x) in enumerate(a):
		if not x in h:
			h[x] = []
		h[x].append(i)
	best = 150001
	for x in h:
		if len(h[x]) > 1:
			l = h[x]
			l.sort()
			for i in range(len(l) - 1):
				if l[i + 1] - l[i] < best:
					best = l[i + 1] - l[i]
	if best == 150001:
		print(-1)
	else:
		print(n - best)


def sol():
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	if len(b) == n:
		print('-1')
	else:
		cns = n
		d = dict()
		for i in b:
			d[i] = []
		for i in range(n):
			d[a[i]].append(i)
		ans = 1500000
		for i in d.keys():
			z = len(d[i])
			if z > 1:
				for j in range(z - 1):
					ans = min(ans, d[i][j + 1] - d[i][j])
		print(cns - ans)
for tt in range(int(input())):
	sol()


def fun(p, a, n, t):
	x = a[1] - a[0]
	for i in range(1, n - 1):
		x = min(x, a[i + 1] - a[i])
	p.append(t - x)
from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(n):
		d[a[i]].append(i)
	p = []
	for i in d:
		if len(d[i]) > 1:
			fun(p, d[i], len(d[i]), n)
	if p == []:
		print(-1)
	else:
		print(max(p))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		if a[i] in d:
			d[a[i]].append(i)
		else:
			d[a[i]] = [i]
	ans = []
	for i in d:
		li = d[i]
		if len(li) >= 2:
			le = len(li)
			for j in range(1, le):
				ans.append(n - li[j] + li[j - 1])
	if ans == []:
		print(-1)
	else:
		print(max(ans))


repeat = int(input())
for j in range(repeat):
	l = int(input())
	num_list = list(map(int, input().split()))
	memo = {}
	for i in range(l):
		if num_list[i] not in memo:
			memo[num_list[i]] = [i, l + 1]
		else:
			if i - memo[num_list[i]][0] < memo[num_list[i]][1]:
				memo[num_list[i]][1] = i - memo[num_list[i]][0]
			memo[num_list[i]][0] = i
	mini = l + 1
	for i in memo:
		if memo[i][1] == 0:
			continue
		if memo[i][1] < mini:
			mini = memo[i][1]
	result = l - mini
	if result == l + 1:
		result = -1
	print(result)


import math

def printDivisors(n):
	i = 1
	l = []
	l1 = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				l.append(i)
			else:
				l.append(i)
				l1.append(n // i)
		i = i + 1
	return l + l1[::-1]

def primeFactors(n):
	s = set()
	while n % 2 == 0:
		s.add(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			s.add(i)
			n = n / i
	if n > 2:
		s.add(n)
	return list(s)

def check(high, fact, primes, mid):
	s = set()
	if mid > len(primes):
		return False
	for ele in primes[:mid]:
		curr = high // ele
		x = curr
		if x in s:
			return False
		s.add(x)
		while x <= high:
			x += curr
			if x in s and x != high:
				return False
			s.add(x)
	return True
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(n):
		d[lis[i]].append(i)
	ans = -1
	for v in d.values():
		for i in range(len(v) - 1):
			ans = max(ans, v[i] - 0 + n - v[i + 1])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	store = {}
	for (i, item) in enumerate(a):
		if store.get(item):
			store[item].append(i)
		else:
			store[item] = [i]
	flag = False
	ans = -1
	for (k, v) in store.items():
		if len(v) > 1:
			for i in range(len(v) - 1):
				if n - v[i + 1] + v[i] > ans:
					ans = n - v[i + 1] + v[i]
	print(ans)


import sys
from math import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a.count(a[0]) == len(a):
		print(n - 1)
	else:
		h = {}
		minn = {}
		for i in range(n):
			if a[i] not in h:
				h[a[i]] = i
				minn[a[i]] = 10 ** 9
			else:
				k = abs(h[a[i]] - i)
				minn[a[i]] = min(minn[a[i]], k)
				h[a[i]] = i
		m = 10 ** 9
		for i in minn:
			m = min(m, minn[i])
		print(n - m) if m != 10 ** 9 else print(-1)


for t in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().split()]
	d = dict()
	for i in range(n):
		if A[i] in d:
			x = i + 1 - d[A[i]][0]
			if x < d[A[i]][1]:
				d[A[i]][1] = x
			d[A[i]][0] = i + 1
		else:
			a = [i + 1, n + 1]
			d[A[i]] = a
	ans = n + 2
	for i in d:
		if d[i][1] < ans:
			ans = d[i][1]
	print(n - ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dict = {}
	checklist = []
	length = -1
	for i in range(n):
		try:
			length = max(length, n - i - 1 + dict[arr[i]][-1] + 1)
			dict[arr[i]].append(i)
		except:
			dict[arr[i]] = [i]
			checklist.append(arr[i])
	print(length)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if arr[i] in d:
			d[arr[i]].append(i)
		else:
			d[arr[i]] = [i]
	ans = 1000000005
	for (i, j) in d.items():
		k = len(j)
		for p in range(1, k):
			ans = min(ans, j[p] - j[p - 1])
	if ans == 1000000005:
		print(-1)
	else:
		print(n - ans)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	f = [-1] * (150000 + 1)
	l = [-1] * (150000 + 1)
	ans = 0
	for i in range(n):
		if f[arr[i]] == -1:
			f[arr[i]] = i
		elif l[arr[i]] == -1:
			l[arr[i]] = i
			ans = max(ans, 1 + f[arr[i]] + n - 1 - l[arr[i]])
		else:
			f[arr[i]] = l[arr[i]]
			l[arr[i]] = i
			ans = max(ans, 1 + f[arr[i]] + n - 1 - l[arr[i]])
	if ans == 0:
		print(-1)
	else:
		print(ans)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	d = dict()
	for i in range(len(l)):
		if l[i] in d:
			d[l[i]].append(i)
		else:
			d[l[i]] = [i]
	ans = -1
	for key in d:
		val = d[key]
		if len(val) > 1:
			for g in range(len(val) - 1):
				ans = max(ans, val[g] + n - val[g + 1])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in range(n):
		x = arr[i]
		if x in d.keys():
			d[x].append(i)
		else:
			d[x] = [i]
	ans = -1
	for a in d.keys():
		pp = d[a]
		if len(pp) == 1:
			continue
		else:
			for i in range(0, len(pp) - 1):
				ans = max(ans, n + pp[i] - pp[i + 1])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if a[i] not in d:
			d[a[i]] = [i]
		else:
			d[a[i]].append(i)
	mn = 100000000000
	for i in d:
		x = len(d[i])
		for j in range(1, x):
			mn = min(mn, d[i][j] - d[i][j - 1])
	if mn == 100000000000:
		print(-1)
	else:
		print(n - mn)


last = {}
for i in range(150001):
	last[i] = -1
t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = -1
	for i in range(n):
		if last[a[i]] != -1:
			ans = max(ans, last[a[i]] + (n - i))
		last[a[i]] = i
	for i in range(n):
		last[a[i]] = -1
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	s = sorted(enumerate(w), key=lambda x: x[1])
	c = 500000
	for i in range(n - 1):
		if s[i][1] == s[i + 1][1]:
			d = abs(s[i][0] - s[i + 1][0])
			if d < c:
				c = d
	print(n - c if c != 500000 else -1)


from _collections import defaultdict
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dic = defaultdict(lambda : [])
	for j in range(n):
		dic[arr[j]].append(j)
	mi = -1
	for el in dic:
		le = len(dic[el])
		for j in range(le - 1):
			fro = dic[el][j]
			bac = n - dic[el][j + 1] - 1
			mi = max(mi, fro + bac + 1)
	print(mi)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	ans = -1
	for i in range(len(a)):
		if a[i] in d:
			ans = max(ans, min(d[a[i]], i) + min(n - d[a[i]], n - i))
			d[a[i]] = i
		else:
			d[a[i]] = i
	print(ans)


import sys
from math import sqrt, gcd
from collections import deque, Counter
sys.setrecursionlimit(10 ** 8)
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	arr = L()
	d = {}
	for i in range(n):
		if arr[i] in d:
			d[arr[i]].append(i)
		else:
			d[arr[i]] = [i]
	ans = float('inf')
	for j in d.values():
		if len(j) >= 2:
			j.sort()
			t = float('inf')
			for i in range(len(j) - 1):
				m = j[i + 1] - j[i]
				if m < t:
					t = m
			if t < ans:
				ans = t
	print(-1 if ans == float('inf') else n - ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	count = {}
	for i in range(n):
		if arr[i] in count:
			count[arr[i]].append(i)
		else:
			count[arr[i]] = [i]
	minm = n + 1
	for i in count:
		x = len(count[i])
		for j in range(x - 1):
			minm = min(minm, count[i][j + 1] - count[i][j])
			if minm == 1:
				break
		if minm == 1:
			break
	print(n - minm)


T = int(input())
for tc in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	D = {}
	for i in range(n):
		if a[i] in D.keys():
			D[a[i]].append(i)
		else:
			D[a[i]] = [i]
	count = 1000000000
	for value in D.values():
		if len(value) >= 2:
			value.sort()
			t = 1000000000
			for i in range(len(value) - 1):
				m = value[i + 1] - value[i]
				if m < t:
					t = m
			if t < count:
				count = t
	if count == 1000000000:
		print(-1)
	else:
		print(n - count)


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	f = dict()
	imp = True
	for i in range(n):
		if a[i] in f:
			f[a[i]].append(i)
			imp = False
		else:
			f[a[i]] = [i]
	if imp:
		ans.append(-1)
		continue
	mx = 1
	for c1 in f:
		c = f[c1]
		if len(c) < 2:
			continue
		closest = 0
		mind = c[1] - c[0]
		for i in range(1, len(c) - 1):
			if c[i + 1] - c[i] < mind:
				mind = c[i + 1] - c[i]
				closest = i
		mx = max(mx, n - c[closest + 1] + c[closest])
	ans.append(mx)
for i in ans:
	print(i)


from collections import Counter
from math import ceil, floor, log, gcd
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())
maximum = 10 ** 6
m = {}
for i in range(maximum):
	m[i] = -1
for _ in range(int(input().strip())):
	n = inp_int()
	a = inp_lis()
	ans = -1
	for i in range(n):
		if m[a[i]] != -1:
			ans = max(ans, n - i - 1 + m[a[i]] + 1)
		m[a[i]] = i
	print(ans)
	for each in a:
		m[each] = -1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	tempDict = {}
	tempset = set([])
	maxLen = -1
	for i in range(n):
		try:
			tempDict[a[i]].append(i)
		except:
			tempset.add(a[i])
			tempDict[a[i]] = [i]
	for i in tempDict:
		if len(tempDict[i]) > 1:
			for j in range(len(tempDict[i]) - 1):
				maxLen = max(maxLen, tempDict[i][j] - tempDict[i][j + 1] + n)
	print(maxLen)


t = int(input())
while t != 0:
	n = int(input())
	a = input().split()
	net = {}
	for i in range(n):
		if a[i] not in net:
			net[a[i]] = [i]
		else:
			net[a[i]].append(i)
	ans = -1
	for i in net:
		if len(net[i]) < 2:
			continue
		x = net[i]
		for j in range(len(x) - 1):
			k1 = x[j]
			k2 = x[j + 1]
			l = min(k1, k2) + min(n - k1, n - k2)
			ans = max(ans, l)
	print(ans)
	t -= 1


def get_number():
	nb_test = int(input())
	return nb_test

def read_case():
	size = int(input())
	tab = list(map(int, input().split()))
	return (tab, size)

def main():
	nb_test = get_number()
	for i in range(nb_test):
		(tab, size) = read_case()
		dico = make_dico(tab)
		ans = find_ans(dico, size)
		print(ans)

def make_dico(tab):
	dico = {}
	for i in range(0, len(tab)):
		str_key = str(tab[i])
		if str_key in dico.keys():
			dico[str_key].append(i)
		else:
			dico[str_key] = [i]
	return dico

def find_closest(tab, size):
	step = size
	if len(tab) != 1:
		for i in range(0, len(tab) - 1):
			buf = tab[i + 1] - tab[i]
			step = min(buf, step)
	return step

def find_ans(dico, size):
	step = size
	for (key, value) in dico.items():
		buf = find_closest(value, size)
		step = min(step, buf)
	if step == size:
		ans = -1
	else:
		ans = size - step
	return ans
main()


t = int(input())
while t != 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	for i in range(n):
		if a[i] not in d.keys():
			d[a[i]] = []
		d[a[i]].append(i)
	maxl = 0
	flag = 0
	for (key, val) in d.items():
		if len(val) > 1:
			flag = 1
	for (keys, val) in d.items():
		if len(val) > 1:
			for i in range(len(val) - 1):
				ans = val[i] - 0 + n - 1 - val[i + 1] + 1
				if ans > maxl:
					maxl = ans
	if flag == 0:
		print(-1)
	else:
		print(maxl)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	z = list(map(int, input().split()))
	ans = -1
	d = dict()
	for i in range(n):
		if z[i] in d:
			d[z[i]].append(i + 1)
		else:
			d[z[i]] = [i + 1]
	k = []
	for i in d.values():
		if len(i) > 1:
			k.append(i)
	l = []
	for i in k:
		p = i[0]
		for j in range(1, len(i)):
			q = i[j]
			s = [p + n - q, p + n - q + 1]
			l.append(min(s))
			p = q
	if len(l) == 0:
		print(-1)
	else:
		print(max(l))


N = int(input())
for _ in range(N):
	n = int(input())
	m = list(map(int, input().split()))
	ans = -1
	dick = {}
	for i in range(n):
		s = m[i]
		dick[s] = dick.get(s, [-1, 0])
		if dick[s][0] < 0:
			dick[s][0] = 1e+32
		elif dick[s][0] >= abs(i - dick[s][1]):
			dick[s][0] = abs(i - dick[s][1])
		dick[s][1] = i
	for s in dick:
		ans = max(ans, n - dick[s][0])
	print(ans)


def solve(length, data):
	s = set(data)
	if len(s) == length:
		return -1
	else:
		indices = {elem: [] for elem in s}
		for (i, elem) in enumerate(data):
			indices[elem].append(i)
		indices = {key: indices[key] for key in indices if len(indices[key]) > 1}
		dict_keys = list(indices.keys())
		memo = indices[dict_keys[0]][1] - indices[dict_keys[0]][0]
		for key in indices:
			for (i, elem) in enumerate(indices[key][1:]):
				if elem - indices[key][i] < memo:
					memo = elem - indices[key][i]
		return length - memo

def do_all():
	solutions = []
	for i in range(int(input())):
		solutions.append(solve(int(input()), [int(c) for c in input().split(' ')]))
	for x in solutions:
		print(x)
do_all()


def fun(n, a):
	lis = []
	ans = []
	for i in range(n):
		lis.append([a[i], i + 1])
	lis.sort(key=lambda x: x[0])
	for j in range(1, n):
		if lis[j][0] == lis[j - 1][0]:
			ans.append(lis[j - 1][1] + (n - lis[j][1]))
	if len(ans) != 0:
		return max(ans)
	return -1
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(fun(n, a))


def give(n, l):
	e = [[l[i], i] for i in range(n)]
	e.sort(key=lambda a: a[0])
	m = -1
	for i in range(n - 1):
		d = 0
		if e[i][0] == e[i + 1][0]:
			d = n - e[i + 1][1] + e[i][1]
		m = max(m, d)
	if m == 0:
		m = -1
	print(m)
for _ in range(int(input())):
	give(int(input()), list(map(int, input().split(' '))))


import math

def findMinDiff(arr, n):
	arr = sorted(arr)
	diff = 10 ** 20
	for i in range(n - 1):
		if arr[i + 1] - arr[i] < diff:
			diff = arr[i + 1] - arr[i]
	return diff
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if l[i] not in d:
			d[l[i]] = [i]
		else:
			d[l[i]].append(i)
	mini = math.inf
	for j in d:
		x = len(d[j])
		mini = min(mini, findMinDiff(d[j], x))
	if n - mini <= 0:
		print(-1)
	else:
		print(n - mini)


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	a = sorted(zip(b, range(n)))
	b = sorted(set(b))
	c = [a[0][1] - n - 1] + [0] * (len(b) - 1)
	i = 0
	y = n + 1
	for (e, x) in a:
		if e == b[i]:
			y = min(y, x - c[i])
			c[i] = x
			if y == 1:
				break
		else:
			i = i + 1
			c[i] = x
	print(n - y)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	ans = -1
	for i in range(n):
		if arr[i] not in d:
			d[arr[i]] = [-1, i, -1]
		else:
			d[arr[i]][0] = d[arr[i]][1]
			d[arr[i]][1] = i
			d[arr[i]][2] = max(d[arr[i]][2], d[arr[i]][0] + (n - (d[arr[i]][1] + 1)) + 1)
		ans = max(ans, d[arr[i]][2])
	print(ans)


from collections import defaultdict
for cases in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	arr = [-1] * 10 ** 6
	ans = -1
	for i in range(0, len(l)):
		if arr[l[i]] != -1:
			ans = max(ans, arr[l[i]] + n - i)
		arr[l[i]] = i
	if ans == n:
		ans = ans - 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if d.get(arr[i]):
			d[arr[i]][0] += 1
			d[arr[i]][1].append(i)
		else:
			d[arr[i]] = [1, [i]]
	best = 0
	flag = False
	for (k, v) in d.items():
		if v[0] <= 1:
			continue
		flag = True
		i = 0
		j = 1
		while j < len(v[1]):
			left = n - 1 - v[1][j]
			right = v[1][i]
			i += 1
			j += 1
			best = max(best, left + right + 1)
	if flag:
		print(best)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	old = [int(k) for k in input().split()]
	new = []
	for i in range(n):
		new.append([old[i], i])
	new.sort()
	k = -1
	for i in range(1, n):
		if new[i][0] == new[i - 1][0]:
			k = max(k, new[i - 1][1] + n - new[i][1])
	print(k)


import math
from sys import stdin
from collections import Counter, deque
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([a[i], i])
	l.sort()
	m = -1
	for i in range(n - 1):
		if l[i][0] == l[i + 1][0]:
			m = max(m, n - (l[i + 1][1] - l[i][1]))
	print(m)


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


from math import inf
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	idx = [-1 for _ in range(150001)]
	short = inf
	for i in range(n):
		k = arr[i]
		if idx[k] != -1:
			short = min(short, i - idx[k])
		idx[k] = i
	if short == inf:
		print(-1)
	else:
		print(n - short)


for _ in range(int(input())):
	n = int(input())
	last_inds = [-1] * 150001
	min_diffs = [150001] * 150001
	i = 0
	for x in input().split():
		x = int(x)
		if last_inds[x] >= 0:
			if i - last_inds[x] < min_diffs[x]:
				min_diffs[x] = i - last_inds[x]
		last_inds[x] = i
		i += 1
	if min(min_diffs) == 150001:
		print(-1)
	else:
		print(n - min(min_diffs))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ele = []
	for i in range(n):
		ele.append([arr[i], i])
	ele.sort()
	maxx = -1
	for i in range(n - 1):
		if ele[i][0] == ele[i + 1][0]:
			maxx = max(maxx, n - ele[i + 1][1] + ele[i][1])
	print(maxx)


for i in range(int(input())):
	length = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	if len(s) == len(l) or len(l) == 1:
		print(-1)
	elif len(s) == 1:
		print(len(l) - 1)
	else:
		newlist = []
		for (i, v) in enumerate(l):
			newlist += [[v, i]]
		newlist.sort()
		max_ = 0
		for i in range(1, length):
			if newlist[i][0] == newlist[i - 1][0]:
				temp = length - newlist[i][1] + newlist[i - 1][1]
				if max_ < temp:
					max_ = temp
		print(max_)


import collections
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = -1
	d = defaultdict(lambda : [])
	for i in range(n):
		d[a[i]].append([i, n - 1 - i])
	for x in d:
		z = d[x]
		for i in range(len(z) - 1):
			ans = max(ans, 1 + min(z[i][0], z[i + 1][0]) + min(z[i][1], z[i + 1][1]))
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	min = 1000000
	w = None
	a = sorted([[l[i], i] for i in range(n)])
	for i in range(n - 1):
		if a[i][0] == a[i + 1][0]:
			if a[i + 1][1] - a[i][1] < min:
				(w, e) = (a[i + 1][1], a[i][1])
				min = w - e
		else:
			i = i + 1
	else:
		if w == None:
			print(-1)
		else:
			print(n - w + e)
	t = t - 1