311236: CF1954B. Make It Ugly

B. Make It Uglytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Let's call an array $a$ beautiful if you can make all its elements the same by using the following operation an arbitrary number of times (possibly, zero):

• choose an index $i$ ($2 \le i \le |a| - 1$) such that $a_{i - 1} = a_{i + 1}$, and replace $a_i$ with $a_{i - 1}$.

You are given a beautiful array $a_1, a_2, \dots, a_n$. What is the minimum number of elements you have to remove from it in order for it to stop being beautiful? Swapping elements is prohibited. If it is impossible to do so, then output -1.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Additional constraints on the input:

• in every test case, the given array $a$ is beautiful;
• the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

Output

For each test case, output a single integer — the minimum number of elements you have to remove from the array $a$ in order for it to stop being beautiful. If it is impossible, then output -1.

ExampleInput

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

Output

-1
1
-1
3

Note

In the first testcase, it is impossible to modify the array in such a way that it stops being beautiful. An array consisting of identical numbers will remain beautiful no matter how many numbers we remove from it.

In the second testcase, you can remove the number at the index $5$, for example.

The resulting array will be $[1, 2, 1, 2]$. Let's check if it is beautiful. Two operations are available:

• Choose $i = 2$: the array becomes $[1, 1, 1, 2]$. No more operations can be applied to it, and the numbers are not all the same.
• Choose $i = 3$ instead: the array becomes $[1, 2, 2, 2]$. No more operations can be applied to it either, and the numbers are still not all the same.

Thus, the array $[1, 2, 1, 2]$ is not beautiful.

In the fourth testcase, you can remove the first three elements, for example. The resulting array $[5, 3, 3, 3]$ is not beautiful.

题目大意：
给定一个“美丽”的数组，可以通过以下操作使所有元素相同：选择一个索引 i (2 ≤ i ≤ |a| - 1) 使得 a_{i-1} = a_{i+1}，然后用 a_{i-1} 替换 a_i。现在要求删除最少的元素，使得数组不再“美丽”。如果无法做到，输出 -1。

输入数据格式：
第一行包含一个整数 t (1 ≤ t ≤ 10^4) —— 测试用例的数量。
每个测试用例的第一行包含一个整数 n (1 ≤ n ≤ 3 × 10^5)。
第二行包含 n 个整数 a_1, a_2, …, a_n (1 ≤ a_i ≤ n)。
输入的数组 a 是“美丽”的；所有测试用例的 n 之和不超过 3 × 10^5。

输出数据格式：
对于每个测试用例，输出一个整数——为了使数组 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

注意：
在第一个测试用例中，无法修改数组使其停止“美丽”。由相同数字组成的数组无论如何删除都会保持“美丽”。
在第二个测试用例中，可以删除索引 5 处的数字，例如。
在第四个测试用例中，可以删除前三个元素，例如。结果数组 [5, 3, 3, 3] 不再“美丽”。题目大意： 给定一个“美丽”的数组，可以通过以下操作使所有元素相同：选择一个索引 i (2 ≤ i ≤ |a| - 1) 使得 a_{i-1} = a_{i+1}，然后用 a_{i-1} 替换 a_i。现在要求删除最少的元素，使得数组不再“美丽”。如果无法做到，输出 -1。 输入数据格式： 第一行包含一个整数 t (1 ≤ t ≤ 10^4) —— 测试用例的数量。 每个测试用例的第一行包含一个整数 n (1 ≤ n ≤ 3 × 10^5)。 第二行包含 n 个整数 a_1, a_2, …, a_n (1 ≤ a_i ≤ n)。 输入的数组 a 是“美丽”的；所有测试用例的 n 之和不超过 3 × 10^5。 输出数据格式： 对于每个测试用例，输出一个整数——为了使数组 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 注意： 在第一个测试用例中，无法修改数组使其停止“美丽”。由相同数字组成的数组无论如何删除都会保持“美丽”。 在第二个测试用例中，可以删除索引 5 处的数字，例如。 在第四个测试用例中，可以删除前三个元素，例如。结果数组 [5, 3, 3, 3] 不再“美丽”。