CF1450F.The Struggling Contestant

To help those contestants who struggle a lot in contests, the headquarters of Codeforces are planning to introduce Division 5. In this new division, the tags of all problems will be announced prior to the round to help the contestants.

The contest consists of $n$ problems, where the tag of the $i$-th problem is denoted by an integer $a_i$.

You want to AK (solve all problems). To do that, you must solve the problems in some order. To make the contest funnier, you created extra limitations on yourself. You do not want to solve two problems consecutively with the same tag since it is boring. Also, you are afraid of big jumps in difficulties while solving them, so you want to minimize the number of times that you solve two problems consecutively that are not adjacent in the contest order.

Formally, your solve order can be described by a permutation $p$ of length $n$. The cost of a permutation is defined as the number of indices $i$ ($1\le i \lt n$) where $|p_{i+1}-p_i| \gt 1$. You have the requirement that $a_{p_i}\ne a_{p_{i+1}}$ for all $1\le i \lt n$.

You want to know the minimum possible cost of permutation that satisfies the requirement. If no permutations meet this requirement, you should report about it.

为了帮助那些在比赛中表现困难的参赛者，Codeforces 总部计划推出“第五分组（Division 5）”。在这一新分组中，所有题目的标签将在比赛开始前公开，以帮助参赛者更好地准备。

本场竞赛共包含 $n$ 道题目，其中第 $i$ 道题的标签用整数 $a_i$ 表示。

你希望达成“AK”（即解决全部题目）。为此，你必须以某种顺序依次解决这些题目。为了让比赛更富趣味性，你为自己额外设定了若干限制条件：

• 你不希望连续解决两个标签相同的题目（因为这很枯燥）；
• 同时，你担心解题过程中难度出现大幅跳跃，因此希望最小化连续求解的两道题目在原始题目顺序中不相邻的次数。

形式化地，你的解题顺序可用一个长度为 $n$ 的排列 $p$ 来描述。该排列的代价定义为满足 $|p_{i+1}-p_i| > 1$ 的下标 $i$ 的个数（其中 $1 \le i < n$）。此外，你还要求对所有 $1 \le i < n$，均有 $a_{p_i} \ne a_{p_{i+1}}$。

你需要求出满足上述约束条件的排列的最小可能代价；若不存在满足条件的排列，则应报告这一点。

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

The first line of the description of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of problems in the contest.

The next line contains $n$ integers $a_1,a_2,\ldots a_n$ ($1 \le a_i \le n$) — the tags of the problems.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

第一行包含一个整数 $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$。

For each test case, if there are no permutations that satisfy the required condition, print $-1$. Otherwise, print the minimum possible cost of a permutation that satisfies the required condition.

对于每个测试用例，若不存在满足要求条件的排列，则输出 $-1$；否则，输出满足要求条件的排列的最小可能代价。

In the first test case, let $p=[5, 4, 3, 2, 1, 6]$. The cost is $1$ because we jump from $p_5=1$ to $p_6=6$, and $|6-1| \gt 1$. This permutation is valid because we don't solve problems with the same tag twice in a row. We cannot find a permutation with a cost smaller than $1$.

In the second test case, let $p=[1,5,2,4,3]$. The cost is $3$ because $|p_2-p_1| \gt 1$, $|p_3-p_2| \gt 1$, and $|p_4-p_3| \gt 1$. The permutation is valid because we don't solve problems with the same tag twice in a row. We cannot find a permutation with a cost smaller than $3$.

In the third test case, for any order of solving the problems, we will solve two problems with the same tag consecutively, so the answer is $-1$.

在第一个测试用例中，令 $p=[5, 4, 3, 2, 1, 6]$。其代价为 $1$，因为我们从 $p_5=1$ 跳转到 $p_6=6$，且 $|6-1| \gt 1$。该排列是合法的，因为我们不会连续解决两个标签相同的题目。不存在代价小于 $1$ 的排列。

在第二个测试用例中，令 $p=[1,5,2,4,3]$。其代价为 $3$，因为 $|p_2-p_1| \gt 1$、$|p_3-p_2| \gt 1$ 且 $|p_4-p_3| \gt 1$。该排列是合法的，因为我们不会连续解决两个标签相同的题目。不存在代价小于 $3$ 的排列。

在第三个测试用例中，无论以何种顺序解决题目，都必然会出现连续解决两个标签相同的题目，因此答案为 $-1$。