The Struggling Contestant
Contest: Codeforces Global Round 12
Difficulty rating: 2400
Tags: constructive algorithms, greedy

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<n$$$) where $$$|p_{i+1}-p_i|>1$$$. You have the requirement that $$$a_{p_i}\ne a_{p_{i+1}}$$$ for all $$$1\le i< 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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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|>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|>1$$$, $$$|p_3-p_2|>1$$$, and $$$|p_4-p_3|>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$$$.

Example input:
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

Example output:
1
3
-1
2

Editorial:
Suppose $$$p$$$ is a permutation that satisfies the condition. Imagine we add a divider between adjacent indices that are not adjacent in $$$p$$$. If $$$k$$$ is the number of "jumps" in $$$p$$$, then we have split the array $$$a$$$ into $$$k+1$$$ consecutive segments. The permutation will scan these segments in some order, and each segment can be scanned in forward or reversed order. We can visualize the problem like we "cut" the array in $$$k$$$ places, then reorder and reverse the segments so that no two adjacent tags are equal.
Obviously, for all $$$i$$$ such that $$$a_i=a_{i+1}$$$ we need to cut between $$$i$$$ and $$$i+1$$$. Now, we only need to think about the endpoints of these segments, and we need a condition for when it is possible to avoid connecting equal endpoints. For a tag $$$x$$$, define $$$f(x)$$$ as the number of times $$$x$$$ appears as an endpoint of a segment. Note that if a segment consists of only one tag, we count $$$x$$$ twice, as both a left and right endpoint.
We claim that a valid reordering of the segments is possible if and only if for all tags $$$x$$$, it holds that $$$f(x) \le k+2$$$.
• Let $$$x$$$ be a tag. Let's prove that if a solution exists, then $$$f(x)\le k+2$$$. Consider a reordering of the segments as $$$[y_1, y_2],[y_3,y_4],\ldots,[y_{2k+1},y_{2k+2}]$$$. Here, $$$y_{2i-1}$$$ and $$$y_{2i}$$$ are the endpoints of the segment that appears $$$i$$$-th in the solution order. Since $$$y_{2i}$$$ and $$$y_{2i+1}$$$ are connected, they cannot both be $$$x$$$. It can be that $$$y_1=x$$$, and it can be that $$$y_{2k+2}=x$$$, but at most half of the remaining endpoints (there are $$$2k$$$ of them) can be $$$x$$$ due to these connections. So $$$f(x)\le k+2$$$.
• Let's prove that if $$$f(x)\le k+2$$$ for all tags $$$x$$$, then we can construct a solution. We proceed by induction on $$$k$$$. If $$$k=0$$$, there is only one segment and we are done. Now, suppose $$$k\ge 1$$$. Let $$$x$$$ be any tag with maximum $$$f(x)$$$. Select one segment with $$$x$$$ as an endpoint and another with $$$y \ne x$$$ as an endpoint. (Note that such a pair of segments always exists). Connect the selected $$$x$$$ and $$$y$$$ together, merging them into one segment. We have reduced the number of segments by $$$1$$$, and we have decreased the frequencies of $$$x$$$ and $$$y$$$ as endpoints by $$$1$$$. After making this connection, the condition clearly holds for $$$x$$$ and $$$y$$$. For all other tags $$$z$$$ ($$$z \ne x$$$, $$$z \ne y$$$), it holds before the operation that $$$f(z) \le (2k+2)-f(x)\le (2k+2)-f(z)$$$ and so $$$f(z)\le k+1$$$. After the operation, $$$k$$$ decreases and $$$f(z)$$$ is unchanged, so $$$f(z) \le k+2$$$ holds. By induction, a solution exists.
To find the solution with the minimum number of cuts, we firstly must cut the array between all adjacent indices of equal tags. If this set of cuts already satisfies the above condition, we are done.
Otherwise, there is a tag $$$x$$$ such that $$$f(x) > k+2$$$ and for all tags $$$y \ne x$$$, $$$f(y)\le k+2$$$. If we add a cut between two consecutive tags such that one of them is $$$x$$$, it increases $$$f(x)$$$ by one and $$$k$$$ by one, so it is useless. If we cut between two consecutive tags that are not $$$x$$$, it does not change $$$f(x)$$$ and it increases $$$k$$$ by one. That is, each such cut brings the condition one step closer to equality. Therefore if a solution exists and $$$f(x)>k+2$$$, we require exactly $$$f(x)-(k+2)$$$ additional cuts.
Let's summarize the solution. If some tag $$$x$$$ has more than $$$\lceil n/2\rceil$$$ occurrences, a solution does not exist. Otherwise, let $$$k$$$ be the number of adjacent equal tags, and add the necessary cuts in these positions. Let $$$x$$$ be the tag that occurs most frequently as an endpoint in the resulting segments. The answer is $$$k+\max\{0, f(x)-(k+2)\}$$$.