解题思路

我们希望通过至多一次删除一个连续子段，使剩余序列所有元素互不相同（“多彩”）。设删除的是区间 $[l,r]$，则保留下来的部分是前缀 $[1,l-1]$ 与后缀 $[r+1,n]$ 的拼接。因此剩余序列“多彩”的充要条件是：

1. 前缀内部互不相同；
2. 后缀内部互不相同；
3. 前缀与后缀之间也没有重复元素。

于是问题转化为：选择一个前缀长度 $i$（保留 $[1,i]$），和一个后缀起点 $r$（保留 $[r,n]$），满足三条互异性条件，删除长度为 $k=r-i-1$ 的中段，使 $k$ 最小。为了便于实现，令前缀长度用“元素个数”记为 $i$（即保留 $[1..i]$），则删除长度是 $r-i$（当我们用 0-based 写法时，等式会相应平移，思想一致）。

题目内容

小明喜欢多彩的数列。在他眼中，一个数列是多彩的，当且仅当数列中的元素互不相同.具体的，数列 $b_1,b_2,…,b_n$ 。被认为是多彩的，当且仅当对于任意两个不同的下标 $i,j(1 ≤i,j≤n,i≠j)$， 都有 $b_i≠b_j$ ;

这天，小明拿到了一个长为 $n$ 的数列 {$a$}。并且，他能选择施展他的魔法，选择一个非负整数 $k$ ，将这个数列中某一个长度为k的连续子段删去(剩下的元素按原顺序拼接)，这个过程消耗 $k$ 个单位的魔力值。

因为施展魔法后小明会变得很虚弱，所以他只能施展该魔法至多一次。当然，如果 {$a$} 原来就是多彩的，他也可以不施展。

你能帮助小明计算，让数列 {$a$} 变得多彩所需的最小魔力值吗?

输入描述

单个测试用例点包含多组数据。

第一行一个正整数 $T$，表示数据组数。

对于接下来的每一组数据:

第一行一个正整数 $n$ 。

第二行 $n$ 个正整数以空格分隔，表示数列 {$a$}.

$1≤\sum n≤2*10^5,1≤a_i≤10^9$.

其中 $∑n$ 表示所有 $T$ 组数据的 $n$ 之和。

输出描述

对于每一组数据，输出一行一个整数，表示让 {$a$} 变得多彩所需的最小魔力值。

样例1

输入

3
10
8 7 1 2 7 6 3 4 6 5
5
10 20 30 40 50
7
1 2 1 3 4 5 6

输出

2
0
1

说明

对于第一组样例，删去区间 $[5,6]$ 能使数列变得多彩，消耗 $2$ 点魔力值。可以证明没有更优的方案。

对于第二组样例，原数列已经多彩，故答案为 $0$ 。