1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 const int Maxn=40010; 8 int Next[Maxn],F[Maxn],a[Maxn],B[Maxn],Last[Maxn],n,m,Top; 9 inline int Min(int x,int y) {return x>y?y:x;}10 int main()11 {12     scanf("%d%d",&n,&m);13     for (int i=1;i<=n;i++) scanf("%d",&a[i]); 14     int Block=floor(sqrt(n));15     for (int i=1;i<=Block;i++) B[i]=1;16     for (int i=1;i<=n;i++)17     {18         Next[i]=Last[a[i]];19         Last[a[i]]=i;20         for (int j=1;j<=Min(Top,Block);j++)21             if (B[j]>Next[i])22             {23                 while (true)24                 {25                     B[j]++;26                     if (B[j]-1==Last[a[B[j]-1]]) break;27                 }28             }29         if (!Next[i]) Top++;30         F[i]=i;31         for (int j=1;j<=Min(Top,Block);j++) F[i]=Min(F[i],F[B[j]-1]+j*j);32     }33     printf("%d\n",F[n]);34     return 0;35 }