为了帮助那些在比赛中遇到困难的选手,Codeforces总部计划推出第5组。在这个新组中,所有问题的标签将在比赛前公布,以帮助参赛者。
竞赛由 $$$n$$$ 问题组成,其中第 $$$i$$$ 问题的标签由整数 $$$a_i$$$ 表示。
你想要AK(解决所有问题)。为此,您必须按某种顺序解决问题。为了让比赛变得更有趣,你给自己设置了额外的限制。您不想使用相同的标签连续解决两个问题,因为这很无聊。此外,您担心在解决问题时难度会大幅跃升,因此您希望尽量减少连续解决两个在竞赛顺序中不相邻的问题的次数。
形式上,您的求解顺序可以通过长度为 $$$n$$$ 的排列 $$$p$$$ 来描述。排列的成本定义为索引 $$$i$$$ ($$$1\le i<n$$$) 的数量,其中 $$$|p_{i+1}-p_i|>1$$$。您的要求是 $$$a_{p_i}\ne a_{p_{i+1}}$$$ 对于所有 $$$1\le i< n$$$。
您想知道满足要求的最小可能排列成本。如果没有排列满足此要求,您应该报告它。
输入
第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$) — 测试用例的数量。
每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 竞赛中的问题数。
下一行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots a_n$$$ ($$$1 \le a_i \le n$$$) — 问题的标签。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,如果没有满足所需条件的排列,则打印 $$$-1$$$。否则,打印满足所需条件的排列的最小可能成本。
示例
输入 #1
4 6 2 1 2 3 1 1 5 1 1 1 2 2 8 7 7 2 7 7 1 8 7 10 1 2 3 4 1 1 2 3 4 1
输出 #1
1 3 -1 2
注意
在第一个测试用例中,令 $$$p=[5, 4, 3, 2, 1, 6]$$$。成本是$$$1$$$,因为我们从$$$p_5=1$$$跳到$$$p_6=6$$$,并且$$$|6-1|>1$$$。这种排列是有效的,因为我们不会连续两次解决相同标签的问题。我们找不到成本小于 $$$1$$$ 的排列。
在第二个测试用例中,令 $$$p=[1,5,2,4,3]$$$。成本为 $$$3$$$,因为 $$$|p_2-p_1|>1$$$、$$$|p_3-p_2|>1$$$ 和 $$$|p_4-p_3|>1$$$。该排列是有效的,因为我们不会连续两次解决具有相同标签的问题。我们找不到成本小于 $$$3$$$ 的排列。
在第三个测试用例中,对于任何解决问题的顺序,我们都会连续解决具有相同标签的两个问题,因此答案是$$$-1$$$。