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