Make It Ugly

题面翻译

有 $t$ 组数据。

定义一次操作：选择一个 $i$ 满足 $2\le i \le n-1$ 且 $a_{i-1}=a_{i+1}$，则可将 $a_i$ 的值修改为 $a_{i-1}$ 的值。

定义一个数列是美丽的，当且仅当该数列进行任意次操作后数列中的所有元素均相等。

现给定一个长度为 $n$ 的美丽的数列 $a$，求使它不美丽至少要删去当中的几个数（不能删完）。若无法完成，输出 $-1$。

Translated by @TachibanaKanade

题目描述

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.

输入格式

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 $ .

输出格式

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.

样例 #1

样例输入 #1

4
3
2 2 2
5
1 2 1 2 1
1
1
7
3 3 3 5 3 3 3

样例输出 #1

-1
1
-1
3

提示

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.

数组必定是a[1]和a[n]是相等的，完美后的数字也是a[1]

1，不断删头或尾，使得头尾不相等
2，找和a[1]不等的数的下标，找下标距离最近的，删掉中间的也就无法完美了

const int N = 3e5 + 10;
int a[N];
int b[N];
void solve()
{
    int n;
    cin >> n;
    int ok = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (i >= 2 && a[i] != a[i - 1]) ok = 1;
    }
    if (ok == 0)
    {
        cout << "-1" << '\n';
        return;
    }
    int to = a[1];
    int h = 0;
    for (int i = 2; i <= n; i++) if (a[i] != to) b[++h] = i;
    int mmin = 1e9;
    for (int i = 2; i <= h; i++) mmin = min(mmin, b[i] - b[i - 1] - 1);
    int l = 0, r = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] != to)
        {
            l = i - 1;
            break;
        }
    }
    for (int i = n; i >= 1; i--)
    {
        if (a[i] != to)
        {
            r = n - i;
            break;
        }
    }
    cout << min(mmin, min(l, r)) << '\n';
}