CF1450F The Struggling Contestant

为了帮助那些在比赛中挣扎的选手，Codeforces 总部计划引入 Division 5。在这个新分区中，所有题目的标签将在比赛前公布，以帮助选手。 比赛包含 $n$ 道题目，第 $i$ 道题目的标签用整数 $a_i$ 表示。 你想要 AK（全部解出）这些题目。为此，你需要以某种顺序解题。为了让比赛更有趣，你给自己增加了额外的限制：你不希望连续解两道标签相同的题目，因为那样很无聊。同时，你也害怕在解题时难度跨度太大，因此你希望最小化连续解两道在原题目顺序中不是相邻题目的次数。 形式化地，你的解题顺序可以用一个长度为 $n$ 的排列 $p$ 表示。排列的代价定义为满足 $1\le i1$ 的 $i$ 的个数。你还需要满足 $a_{p_i}\ne a_{p_{i+1}}$ 对于所有 $1\le i< n$。 你想知道满足要求的排列的最小可能代价。如果不存在满足要求的排列，输出 $-1$。

第一行包含一个整数 $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$。否则，输出满足要求的排列的最小可能代价。

在第一个测试用例中，令 $p=[5, 4, 3, 2, 1, 6]$。代价为 $1$，因为从 $p_5=1$ 跳到 $p_6=6$ 时 $|6-1|>1$。该排列有效，因为没有连续解标签相同的题目。无法找到代价更小的排列。 在第二个测试用例中，令 $p=[1,5,2,4,3]$。代价为 $3$，因为 $|p_2-p_1|>1$，$|p_3-p_2|>1$，$|p_4-p_3|>1$。该排列有效，因为没有连续解标签相同的题目。无法找到代价更小的排列。 在第三个测试用例中，无论如何排列，总会有连续两道题标签相同，因此答案为 $-1$。 由 ChatGPT 4.1 翻译