题目描述

我们称一个数组 $a$ 是“美丽的”，如果你可以通过任意次数（可能为零）以下操作使得所有元素都相同：

• 选择一个下标 $i$（$2 \le i \le |a| - 1$），且满足 $a_{i - 1} = a_{i + 1}$，然后将 $a_i$ 替换为 $a_{i - 1}$。

给定一个美丽的数组 $a_1, a_2, \dots, a_n$，你需要求出最少需要删除多少个元素，才能使它不再是美丽的？禁止交换元素。如果无法做到，请输出 $-1$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。

输入的额外约束：

• 每个测试用例中，给定的数组 $a$ 都是美丽的；
• 所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示最少需要删除多少个元素才能使数组 $a$ 不再是美丽的。如果无法做到，输出 $-1$。

输入输出样例 #1

输入 #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
-1
3

说明/提示

在第一个测试用例中，不可能将数组修改为不美丽。一个由相同数字组成的数组，无论删除多少个数字，仍然是美丽的。

在第二个测试用例中，你可以删除下标为 $5$ 的数字。

得到的新数组为 $[1, 2, 1, 2]$。我们来检查它是否美丽。可用的两种操作：

• 选择 $i = 2$：数组变为 $[1, 1, 1, 2]$。无法再进行操作，且数字并不全相同。
• 选择 $i = 3$：数组变为 $[1, 2, 2, 2]$。同样无法再进行操作，且数字也不全相同。

因此，数组 $[1, 2, 1, 2]$ 不是美丽的。

在第四个测试用例中，你可以删除前面三个元素。例如，得到的新数组 $[5, 3, 3, 3]$ 不是美丽的。