题目描述

数组如何不完美？。

如果你可以通过任意次数（可能是零）的以下操作使数组中的所有元素都相同的话，那么这个数组就是完美数组。

操作：选择一个$a_{i-1}=a_{i+1}$的索引$i$($2 \le i \le |a|-1$,$|a|$表示数组$a$的大小),并将$a_i$替换为$a_{i-1}$。 给你一个完美数组$a$,至少要删除多少个元素才能使数组不再完美？如果不可能，输出-1。

输入

第一行包含一个整数$t$($1 \le t \le 10^4$)

每个测试用例的第一行包含一个整数$n$($1 \le n \le 3 \times 10^4$) 第二行包含$n$个整数$a_i$($1 \le a_i \le n$) 输入限制：

在每个测试样例中，给定的数组a都是完美数组。

所有测试用例中n的总和不超过 $3 \times 10^5$

输出

对于每个测试用例，输出一个整数--为了使数组 $a$ 不再完美，你必须从数组 $a$ 中移除的最少的元素个数。如果不可能，那么输出 -1。

样例

4
3
2 2 2
5
1 2 1 2 1
1
1
7
3 3 3 5 3 3 3

-1
1
-1
3