# Codeforces868f yet another minimizationproblem

Posted by yjjr's blog on February 6, 2018 2 minutes to read

You are given an array ofn integersa1... an. The cost of a subsegment is thenumber of unordered pairs of distinct indices within the subsegment thatcontain equal elements. Split the given array intok non-intersectingnon-empty subsegments so that the sum of their costs is minimum possible. Eachelement should be present in exactly one subsegment.

Input

The first line contains two integersnand k (2 ≤ n ≤ 105, 2 ≤ k ≤ min (n, 20))  — the length of the array and the number of segments youneed to split the array into.

The next line containsn integers a1, a2, ..., an (1 ≤ ai ≤ n) — the elements of the array.

Output

Print single integer: the minimum possibletotal cost of resulting subsegments.

Examples

Input

7 3
1 1 3 3 3 2 1

Output

1

Input

10 2
1 2 1 2 1 2 1 2 1 2

Output

8

Input

13 3
1 2 2 2 1 2 1 1 1 2 2 1 1

Output

9

Note

In the first example it's optimal to splitthe sequence into the following three subsegments: [1], [1, 3], [3, 3, 2, 1]. The costs are 0, 0 and 1, thus the answer is 1.

In the second example it's optimal to splitthe sequence in two equal halves. The cost for each half is 4.

In the third example it's optimal to splitthe sequence in the following way: [1, 2, 2, 2, 1], [2, 1, 1, 1, 2], [2, 1, 1]. The costs are 4,4, 1.

F数组记录答案，g数组记录二分时的状态

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL unsigned long long
using namespace std;
const int maxn=100006,inf=0x3f3f3f;
int n,k,a[maxn],t[maxn],p,q;
LL f[maxn],g[maxn],now;//防止答案过大，用long long存储

void solve(int l1,int r1,int l2,int r2){
//以l1,r1为标准范围进行二分
if(l1>r1)return;
int mid=(l1+r1)/2,temp=min(r2,mid);
LL mv=1e19;
while(q<mid)now+=t[a[++q]]++;
while(p>temp+1)now+=t[a[--p]]++;
while(q>mid)now-=--t[a[q--]];
while(p<temp+1)now-=--t[a[p++]];//使p,q不断接近now和temp+1
dep(i,temp,l2){
int x=a[i];
now+=t[a[--p]]++;
if(now+f[i-1]<mv)mv=now+f[i-1],temp=i;//选取最小的now+f[i-1]替换mv
}
g[mid]=mv;
solve(l1,mid-1,l2,temp);
solve(mid+1,r1,temp,r2);
}
int main()
{
scanf("%d%d",&n,&k);
rep(i,1,n)scanf("%d",&a[i]);
mem(f,inf);
f[0]=0;
rep(i,1,k){
p=1,q=now=0;
mem(t,0);
solve(i,n,i,n);
memcpy(f,g,sizeof f);
}
printf("%I64d\n",f[n]);
return 0;
}