#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=450;
int n,m,i,j,a[N],b[N],k;
int l[M],cnt[M][N],p[M];
int dp[N],t,pp,res,c[N];
struct FSI {
	template<typename T>
	FSI& operator >> (T &res) {
		res = 0; T f = 1; char ch = getchar();
		while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
		while (isdigit(ch)) {res = res * 10 + ch - '0'; ch = getchar();}
		res *= f;
		return *this;
	}
}scan;
inline int minn(int x,int y){return x>y?y:x;}
int main()
{
	scan>>n;
	for (i=1;i<=n;i++) scan>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	k=unique(b+1,b+n+1)-b-1;
	t=sqrt(n);
	for (i=1;i<=n;i++) a[i]=lower_bound(b+1,b+k+1,a[i])-b;
	for (i=1;i<=t;i++) l[i]=1;
	for (i=1;i<=n;i++)
	{
		pp=a[i];
		if (!c[pp]) res++;
		c[pp]++;
		for (j=1;j<=t;j++)
		{
			if (!cnt[j][pp])
			{
				p[j]++;
				while (l[j]<=i&&p[j]>j)
				{
					k=a[l[j]];
					cnt[j][k]--;
					if (!cnt[j][k]) p[j]--;
					l[j]++;
				}
			}
			cnt[j][pp]++;
		}
		dp[i]=i;
		for (j=1;j<=res&&j<=t;j++) dp[i]=minn(dp[i],dp[l[j]-1]+j*j);
	}
	printf("%d",dp[n]);
	return 0;
}

《不如暴力》