#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll n,k,a[35005],last[35005];
ll d[105][35005];
struct Item{
	ll min,add,orig;
}s[120005],ans;
void build(int u,int L,int R){
	s[u].add=0;
	if(L==R){s[u].min=s[u].orig=a[L];return;}
	int M=(L+R)/2;
	build(u*2,L,M);build(u*2+1,M+1,R);
	s[u].min=min(s[u*2].min,s[u*2+1].min);
}
void maintain(int u,int L,int R){
	s[u].min=s[u].orig;
	if(L<R)s[u].min=min(s[u*2].min,s[u*2+1].min);
	s[u].min+=s[u].add;
}	
void update(int u,int L,int R,int ql,int qr,int v){
	if(ql<=L&&R<=qr){
		s[u].add+=v;
		maintain(u,L,R);return;
	}int M=(L+R)/2;
	if(ql<=M)update(u*2,L,M,ql,qr,v);
	if(M<qr)update(u*2+1,M+1,R,ql,qr,v);
	maintain(u,L,R);
}
void query(int u,int L,int R,int ql,int qr,int add=0){
	if(ql<=L&&R<=qr){ans.min=min(ans.min,s[u].min+add);return;}
	int M=(L+R)/2;
	if(ql<=M)query(u*2,L,M,ql,qr,add+s[u].add);
	if(M<qr)query(u*2+1,M+1,R,ql,qr,add+s[u].add);
}
	
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	map<ll,ll>mp;
	for(int i=1;i<=n;i++){
		if(!mp.count(a[i]))last[i]=-1;
		else last[i]=mp[a[i]];
		mp[a[i]]=i;
	}
	d[1][1]=0;
	for(int j=2;j<=n;j++){
		d[1][j]=d[1][j-1];
		if(last[j]!=-1)d[1][j]+=j-last[j];
	}for(int i=2;i<=k;i++){
		for(int j=1;j<=n;j++)a[j]=d[i-1][j];
		build(1,1,n);
		for(int j=1;j<i;j++)d[i][j]=inf;
		d[i][i]=0;
		for(int j=i+1;j<=n;j++){
			if(last[j]!=-1&&i-1<=last[j]-1)
				update(1,1,n,i-1,last[j]-1,j-last[j]);
			ans.min=inf;
			query(1,1,n,i-1,j-1);d[i][j]=ans.min;
		}
	}cout<<d[k][n]<<endl;
	return 0;
}
 					  			 			 						 				  	
### Prompt

Generate a Cpp solution to the following problem:

You are given an array a of n integers. Define the cost of some array t as follows:

$$$cost(t) = ∑_{x ∈ set(t) } last(x) - first(x),$$$ 

where set(t) is the set of all values in t without repetitions, first(x), and last(x) are the indices of the first and last occurrence of x in t, respectively. In other words, we compute the distance between the first and last occurrences for each distinct element and sum them up.

You need to split the array a into k consecutive segments such that each element of a belongs to exactly one segment and the sum of the cost of individual segments is minimum.

Input

The first line contains two integers n, k (1 ≤ n ≤ 35 000, 1 ≤ k ≤ min(n,100)).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n).

Output

Output the minimum sum of the cost of individual segments.

Examples

Input


7 2
1 6 6 4 6 6 6


Output


3


Input


7 4
5 5 5 5 2 3 3


Output


1

Note

In the first example, we can divide the array into [1,6,6,4] and [6,6,6]. Cost of [1,6,6,4] will be (1-1) + (3 - 2) + (4-4) = 1 and cost of [6,6,6] will be 3-1 = 2. Total cost would be 1 + 2 = 3.

In the second example, divide the array into [5,5],[5],[5,2,3] and [3]. Total Cost would be 1 + 0 + 0 + 0 = 1.

### Response

```cpp
#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll n,k,a[35005],last[35005];
ll d[105][35005];
struct Item{
	ll min,add,orig;
}s[120005],ans;
void build(int u,int L,int R){
	s[u].add=0;
	if(L==R){s[u].min=s[u].orig=a[L];return;}
	int M=(L+R)/2;
	build(u*2,L,M);build(u*2+1,M+1,R);
	s[u].min=min(s[u*2].min,s[u*2+1].min);
}
void maintain(int u,int L,int R){
	s[u].min=s[u].orig;
	if(L<R)s[u].min=min(s[u*2].min,s[u*2+1].min);
	s[u].min+=s[u].add;
}	
void update(int u,int L,int R,int ql,int qr,int v){
	if(ql<=L&&R<=qr){
		s[u].add+=v;
		maintain(u,L,R);return;
	}int M=(L+R)/2;
	if(ql<=M)update(u*2,L,M,ql,qr,v);
	if(M<qr)update(u*2+1,M+1,R,ql,qr,v);
	maintain(u,L,R);
}
void query(int u,int L,int R,int ql,int qr,int add=0){
	if(ql<=L&&R<=qr){ans.min=min(ans.min,s[u].min+add);return;}
	int M=(L+R)/2;
	if(ql<=M)query(u*2,L,M,ql,qr,add+s[u].add);
	if(M<qr)query(u*2+1,M+1,R,ql,qr,add+s[u].add);
}
	
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	map<ll,ll>mp;
	for(int i=1;i<=n;i++){
		if(!mp.count(a[i]))last[i]=-1;
		else last[i]=mp[a[i]];
		mp[a[i]]=i;
	}
	d[1][1]=0;
	for(int j=2;j<=n;j++){
		d[1][j]=d[1][j-1];
		if(last[j]!=-1)d[1][j]+=j-last[j];
	}for(int i=2;i<=k;i++){
		for(int j=1;j<=n;j++)a[j]=d[i-1][j];
		build(1,1,n);
		for(int j=1;j<i;j++)d[i][j]=inf;
		d[i][i]=0;
		for(int j=i+1;j<=n;j++){
			if(last[j]!=-1&&i-1<=last[j]-1)
				update(1,1,n,i-1,last[j]-1,j-last[j]);
			ans.min=inf;
			query(1,1,n,i-1,j-1);d[i][j]=ans.min;
		}
	}cout<<d[k][n]<<endl;
	return 0;
}
 					  			 			 						 				  	
```