题目描述

让我们把一个数组 $a$ 称作美丽的数组，如果你能通过任意次数(可能是零)的下面操作使数组中的所有元素都相同的话：

• 选择一个索引 $i(2\le i\le |a|-1，a_{i-1}=a_{i+1})$ ，然后将 $a_i$ 替换为 $a_{i-1}$ 。

给你一个漂亮的数组 $a_1,a_2,...,a_n$，要使数组不再美丽，至少要删除多少个元素？禁止交换元素。如果不可能这样做，那么输出 $-1$。

输入格式

第一行包含一个整数 $n(1\le n\le 3\ast 10^5)$。

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n(1\le a_i\le n)$。

输出格式

输出一个整数–为了使数组 $a$ 不再美丽，你必须从数组 $a$ 中移除的最小元素数。
如果不可能，那么输出 -1。

样例输入1

3
2 2 2

样例输出1

-1

样例输入2

5
1 2 1 2 1

样例输出2

1

样例输入3

7
3 3 3 5 3 3 3

样例输出3

3

提交链接

https://hydro.ac/d/lp728/p/16

提示

保证输入的 $a$ 数组为美丽的数组。

样例解释:
在第一个测试案例中，不可能通过修改数组的方式使其不再美丽。无论我们从数组中删除多少数字，由相同数字组成的数组都会保持美丽。

在第二个测试案例中，你可以删除索引 $5$ 中的数字。这样得到的数组将是 $[1,2,1,2]$ 让我们看看它是否美丽。有两种操作可供选择：

• 选择 $i=2$：数组变为 $[1,1,1,2]$。不能再对其进行其他操作，而且数字也不尽相同。
• 选择 $i=3$：数组变为 $[1,2,2,2,]$。也不能对其进行更多的运算，数字仍然不完全相同。

因此，数组 $[1,2,1,2]$ 并不美观。

在第三个测试用例中，可以删除前三个元素。这样得到的数组 $[5,3,3,3]$ 并不美观。

解析

数组 $a$ 为美丽数组，则一定能是所有的元素都相同，即 $a[i]=x$。

我们在变换一致的过程中，能选择的下标的范围为 $2\le i\le |a|-1$ ，是无法对 $a[1]$ 或 $a[n]$ 来进行操作的。所以我们可以得出 $x$ 一定是等于 $a[1]$。

如何让数组不再美丽，可以的操作有：

• 删除等于 $a[1]$ 的整个数字前缀
• 删除等于 $a[1]$ 的整个数字后缀
• 选择两个不等于 $a[1]$ 的数字，删除它们之间的所有数字，使这两个数字相邻。

答案变为：找出等于 $a[1]$ 的最短数块。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 9;
int t , n , a[maxn];
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	int idx = a[1];
	int mi = 9999999 , len = 0;
	for(int i = 1; i <= n; i++)
	{
		if(a[i] == idx)
			len++;
		else
		{
			mi = min(mi , len);
			len = 0;
		}
	}
	mi = min(mi , len);
	if(mi != n)
		cout << mi << endl;
	else
		cout << -1 << endl;
	return 0;
}