Make It Ugly
Contest: Educational Codeforces Round 164 (Rated for Div. 2)
Difficulty rating: 1200
Tags: implementation, math

Let's call an array $$$a$$$ beautiful if you can make all its elements the same by using the following operation an arbitrary number of times (possibly, zero):

- choose an index $$$i$$$ ($$$2 \le i \le |a| - 1$$$) such that $$$a_{i - 1} = a_{i + 1}$$$, and replace $$$a_i$$$ with $$$a_{i - 1}$$$.

You are given a beautiful array $$$a_1, a_2, \dots, a_n$$$. What is the minimum number of elements you have to remove from it in order for it to stop being beautiful? Swapping elements is prohibited. If it is impossible to do so, then output -1.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

Additional constraints on the input:

- in every test case, the given array $$$a$$$ is beautiful;
- the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the minimum number of elements you have to remove from the array $$$a$$$ in order for it to stop being beautiful. If it is impossible, then output -1.

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

Note:
In the first testcase, it is impossible to modify the array in such a way that it stops being beautiful. An array consisting of identical numbers will remain beautiful no matter how many numbers we remove from it.

In the second testcase, you can remove the number at the index $$$5$$$, for example.

The resulting array will be $$$[1, 2, 1, 2]$$$. Let's check if it is beautiful. Two operations are available:

- Choose $$$i = 2$$$: the array becomes $$$[1, 1, 1, 2]$$$. No more operations can be applied to it, and the numbers are not all the same.
- Choose $$$i = 3$$$ instead: the array becomes $$$[1, 2, 2, 2]$$$. No more operations can be applied to it either, and the numbers are still not all the same.

Thus, the array $$$[1, 2, 1, 2]$$$ is not beautiful.

In the fourth testcase, you can remove the first three elements, for example. The resulting array $$$[5, 3, 3, 3]$$$ is not beautiful.

Example input:
4
3
2 2 2
5
1 2 1 2 1
1
1
7
3 3 3 5 3 3 3

Example output:
-1
1
-1
3

Editorial:
As given in the problem statement, the definition of a beautiful array is not very interesting to us, since checking the beauty of an array is quite complex. Let's try to simplify it.
First of all, the first and last elements will never be changed, as it is impossible to choose such $$$i$$$ for operations. If they are different, then the array is definitely not beautiful. Moreover, if the array is beautiful, then all its elements at the end will be equal to the first and the last elements.
The second idea is a bit more complicated. Notice that each element can be changed at most once. Consider an arbitrary operation. We choose some $$$i$$$ for which $$$a_{i - 1} = a_{i + 1}$$$, and change $$$a_i$$$ to $$$a_{i - 1}$$$. Now both $$$a_{i - 1}$$$ and $$$a_{i + 1}$$$ will always remain equal to their current values, because in any operation involving them, $$$a_i$$$ will also be involved. This means that $$$a_i$$$ will also remain equal to the new value.
The next idea is as follows. We know what all the elements should be equal to in the end. This means that we need to apply operations to all elements that are not equal to this value. According to the previous idea, this is possible if and only if there are no two consecutive numbers in the array that are not equal to this value. The sufficiency of this condition is obvious, and the necessity is left as an exercise to the reader.
In other words, the check looks like this: $$$a_1 = a_n$$$, and $$$a_i = a_1$$$ or $$$a_{i + 1} = a_1$$$ (or both are equal) for all $$$i$$$.
What elements should be removed so that the check does not pass? There are two options: break the first or second condition. So, you can do the following:
• remove the entire prefix of numbers equal to $$$a_1$$$;
• remove the entire suffix of numbers equal to $$$a_1$$$ (or $$$a_n$$$ — they are equal to each other, since the given array is beautiful);
• choose two numbers that are not equal to $$$a_1$$$, and remove all the numbers between them, so that these two numbers become adjacent.
The third condition can be simplified. If other numbers not equal to $$$a_1$$$ are encountered between the selected numbers, then another pair can be chosen, for which fewer numbers have to be removed. Therefore, it is only optimal to choose a pair for which all the numbers between them are equal to $$$a_1$$$.
Then the solution is as follows. Find the shortest block of numbers equal to $$$a_1$$$. Remove it from the array. It can be at the prefix or at the suffix — then the first condition will be broken. Or it can be somewhere in the middle — then the second condition will be broken.
To find such a block, you can go through the array from left to right, maintaining the position of the previous element not equal to $$$a_1$$$. If the current element is not equal to $$$a_1$$$, update the answer with the difference between the saved and current positions, and update the saved position.
The only case when the answer is -1 is when all the elements of the array are the same. Otherwise, it is always possible to make the array not beautiful.
Overall complexity: $$$O(n)$$$ for each testcase.