解题思路

我们希望通过至多一次删除一个连续子段，使剩余序列所有元素互不相同（“多彩”）。

等价变形：删除子段 $[l, r-1]$ 后，剩下的是前缀 $a[0..l-1]$ 与后缀 $a[r..n-1]$。要想整体无重复，必须同时满足：

1. 前缀内部无重复；
2. 后缀内部无重复；
3. 前缀元素集合与后缀元素集合不相交。

题目内容

小明喜欢多彩的数列。在他眼中，一个数列是多彩的，当且仅当数列中的元素互不相同。

具体的，数列 $b_1,b_2,…,b_n$ 。被认为是多彩的，当且仅当对于任意两个不同的下标 $ij(1≤i,j≤n,i≠j)$ ，都有 $b_i≠b_j$ 。

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

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

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

输入描述

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

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

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

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

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

$1≤Σ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$ 。