平方级的朴素动态规划很容易想到，定义 $f(i)$ 为到第 $i$ 头牛的最小混乱程度，外层循环牛，内层循环从哪一个状态转移。

考虑优化转移。结果一定不会超过 $n$，因为可以每头牛成一组。那么，每一段内不同数的个数一定 $\le \sqrt{n}$。

转移可以循环不同数的个数 $j$，而不是转移的下标，由上述分析得，这个个数不能超过 $\sqrt{n}$。记 $pos_i$ 表示段内有 $i$ 个不同数的左端点位置。用桶记录，对于每个 $j$，这一段内数的出现情况。如果我们用 $cnt$ 统计的不同数个数超过 $j$，就要从这一段的头部弹出若干数直至满足要求。这时改变 $cnt$ 和 $pos$。这样，我们使用 $pos$，就能快速追溯到应该从哪个下标转移。

// P2943 [USACO09MAR]Cleaning Up G
#include <bits/stdc++.h>
#define pb push_back
#define rep(i, s, t) for(int i=s; i<=t; i++)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cout<<#x<<":"<<x<<endl;
const int SIZE=40005;
using namespace std;

int n, m;
int a[SIZE], f[SIZE], siz;
int c[205][SIZE], pos[205], cnt[205];

signed main()
{
	scanf("%d %d", &n, &m);
	siz=sqrt(n)+1;
	rep(i, 1, n) scanf("%d", a+i);
	memset(f, 0x3f, sizeof(f));
	f[0]=0;
	rep(i, 1, n)
		rep(j, 1, siz)
		{
			c[j][a[i]]++;
			if(c[j][a[i]]==1)
			{
				cnt[j]++;
				if(cnt[j]>j)
				{
					while(--c[j][a[pos[j]++]]!=0) ;
					cnt[j]=j;
				}
			}
			if(cnt[j]==j) f[i]=min(f[i], f[pos[j]-1]+j*j);
		}
	printf("%d", f[n]);

    return 0;
}