/*因为这个题目分组是没有限制的，所以我们DP方程不能把分组作为一个状态

 正解：最差情况每个数位于一段，ans=n，所以若有一段区间内不同的数的数量<=sqrt(n)，否则结果一定不是最优。

 nsqrt（n）求法：维护b[j],c[j],f[j],pre[j]数组。

 b[j]表示b[j]+1...i有j个不同的数的区间的最左端。

 那么可以知道f[i]=min{f[i],f[b[j]]+j*j};这样时间复杂度就降了下来

 如何维护b[j]数组，当i向后移动一位的时候，pre[a[i]]记录a[i]出现的最后一个位置是哪里？

 那么：i++后，pre[a[i]]<=b[j]，说明b[j]+1...到i这段序列的不同数的数目就是j+1了，我们用c[j]来记录这个情况，顺便更新pre[a[i]],而且始终维护c[j]==j;

 那么b[j]仍然是符合题意的。

 维护c[j]就要从b[j]+1开始向后面删除数据，删除时判断若pre[a[t]]>t，则说明是删除了相同的数，对于最后的和谐值没有影响，所以还要删数

 知道pre[a[t]]<=t，删除a[t]，顺便更新b[j]的位置

 */

 #define N 40100

 #include<iostream>

 using namespace std;

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 int f[N],b[N],c[N],pre[N],a[N];

 int n,m;

 void input()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;++i)

       scanf("%d",&a[i]);

     memset(pre,-,sizeof(pre));/*别忘了设置为-1，因为下面会与b[j]==0的初值进行比较*/

     memset(f,,sizeof(f));

 }

 void chuli()

 {

     int sqrtn=sqrt(n+0.5);

     f[]=;/*初始化，前0个数的不和谐值为0，*/

     for(int i=;i<=n;++i)

     {

         for(int j=;j<=sqrtn;++j)

         {

             if(pre[a[i]]<=b[j])

               c[j]++;/*统计新加入的数是不是符合要求*/

         }

         pre[a[i]]=i;/*更新pre*/

         for(int j=;j<=sqrtn;++j)

         {

             if(c[j]>j)/*删除数，缩短序列*/

             {

                 int t=b[j]+;

                 while(pre[a[t]]>t) ++t;

                 b[j]=t;c[j]--;

             }

         }

         for(int j=;j<=sqrtn;++j)

           f[i]=min(f[i],f[b[j]]+j*j);/*更新f*/

     }

 }

 int main()

 {

     input();

     chuli();

     cout<<f[n]<<endl;

     return ;

 }

 /*这个题目既然不以划分次数为状态，那么可以考虑，划分序列的长度*/