← 返回题目列表

Codeforces · 1954/B

B. 让它变得丑陋

中文机器翻译题面 查看原题

如果您可以通过使用以下操作任意次数(可能为零)使其所有元素相同,那么我们称数组 $$$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 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$)。

输入的附加限制:

- 在每个测试用例中,给定的数组 $$$a$$$ 都很漂亮;
- 所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 您必须从数组 $$$a$$$ 中删除的最小元素数量,以使其不再美观。如果不可能,则输出-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]$$$ 并不漂亮。