//
//                       _oo0oo_
//                      o8888888o
//                      88" . "88
//                      (| -_- |)
//                      0\  =  /0
//                    ___/`---'\___
//                  .' \\|     |// '.
//                 / \\|||  :  |||// \
//                / _||||| -:- |||||- \
//               |   | \\\  -  /// |   |
//               | \_|  ''\---/''  |_/ |
//               \  .-\__  '-'  ___/-. /
//             ___'. .'  /--.--\  `. .'___
//          ."" '<  `.___\_<|>_/___.' >' "".
//         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
//         \  \ `_.   \_ __\ /__ _/   .-` /  /
//     =====`-.____`.___ \_____/___.-`___.-'=====
//                       `=---='

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF emplace_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
#define lc (x<<1)
#define rc ((x<<1)|1)
using namespace std;
int n,m;
int mini[1<<17],dp[35005],lst[35005],a[35005],add[1<<17];
void build(int x,int l,int r){
	add[x]=0;
	if(l==r){
		mini[x]=dp[l];RE;
	}
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	mini[x]=min(mini[lc],mini[rc]);
}
void pushdown(int x){
	add[lc]+=add[x];
	add[rc]+=add[x];
	mini[lc]+=add[x];
	mini[rc]+=add[x];
	add[x]=0; 
}
void update(int x,int l,int r,int tl,int tr,int num){
	if(l>=tl&&r<=tr){
		mini[x]+=num;add[x]+=num;
		RE;
	}
	if(l>tr||tl>r)RE ;
	pushdown(x);
	int mid=(l+r)>>1;
	update(lc,l,mid,tl,tr,num);
	update(rc,mid+1,r,tl,tr,num);
	mini[x]=min(mini[lc],mini[rc]);
}
int get(int x,int l,int r,int tl,int tr){
	if(l>=tl&&r<=tr){
		RE mini[x];
	}
	if(l>tr||tl>r)RE 1e9;
	pushdown(x);
	int mid=(l+r)>>1;
	RE min(get(lc,l,mid,tl,tr),get(rc,mid+1,r,tl,tr));
}
void solve(){
	cin>>n>>m;
	FOR(i,1,n){
		int x;
		cin>>x;a[i]=x;
		dp[i]=dp[i-1];
		if(lst[x])dp[i]+=i-lst[x];
		lst[x]=i;
	}
	rep(i,1,m){
		build(1,0,n);
		FILL(lst,0);
		FOR(j,1,n){
			if(lst[a[j]]){
//				cout<<get(1,0,n,0,lst[a[j]]-1)<<' ';
				update(1,0,n,0,lst[a[j]]-1,j-lst[a[j]]);
//				cout<<get(1,0,n,0,lst[a[j]]-1)<<'\n';
			}
			lst[a[j]]=j;
			dp[j]=get(1,0,n,0,j-1);
		}
//		cout<<'\n';
	}
	cout<<dp[n]<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	t=1;
	while(t--)solve();
	RE 0;
}


### Prompt

Your task is to create 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
//
//                       _oo0oo_
//                      o8888888o
//                      88" . "88
//                      (| -_- |)
//                      0\  =  /0
//                    ___/`---'\___
//                  .' \\|     |// '.
//                 / \\|||  :  |||// \
//                / _||||| -:- |||||- \
//               |   | \\\  -  /// |   |
//               | \_|  ''\---/''  |_/ |
//               \  .-\__  '-'  ___/-. /
//             ___'. .'  /--.--\  `. .'___
//          ."" '<  `.___\_<|>_/___.' >' "".
//         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
//         \  \ `_.   \_ __\ /__ _/   .-` /  /
//     =====`-.____`.___ \_____/___.-`___.-'=====
//                       `=---='

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF emplace_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
#define lc (x<<1)
#define rc ((x<<1)|1)
using namespace std;
int n,m;
int mini[1<<17],dp[35005],lst[35005],a[35005],add[1<<17];
void build(int x,int l,int r){
	add[x]=0;
	if(l==r){
		mini[x]=dp[l];RE;
	}
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	mini[x]=min(mini[lc],mini[rc]);
}
void pushdown(int x){
	add[lc]+=add[x];
	add[rc]+=add[x];
	mini[lc]+=add[x];
	mini[rc]+=add[x];
	add[x]=0; 
}
void update(int x,int l,int r,int tl,int tr,int num){
	if(l>=tl&&r<=tr){
		mini[x]+=num;add[x]+=num;
		RE;
	}
	if(l>tr||tl>r)RE ;
	pushdown(x);
	int mid=(l+r)>>1;
	update(lc,l,mid,tl,tr,num);
	update(rc,mid+1,r,tl,tr,num);
	mini[x]=min(mini[lc],mini[rc]);
}
int get(int x,int l,int r,int tl,int tr){
	if(l>=tl&&r<=tr){
		RE mini[x];
	}
	if(l>tr||tl>r)RE 1e9;
	pushdown(x);
	int mid=(l+r)>>1;
	RE min(get(lc,l,mid,tl,tr),get(rc,mid+1,r,tl,tr));
}
void solve(){
	cin>>n>>m;
	FOR(i,1,n){
		int x;
		cin>>x;a[i]=x;
		dp[i]=dp[i-1];
		if(lst[x])dp[i]+=i-lst[x];
		lst[x]=i;
	}
	rep(i,1,m){
		build(1,0,n);
		FILL(lst,0);
		FOR(j,1,n){
			if(lst[a[j]]){
//				cout<<get(1,0,n,0,lst[a[j]]-1)<<' ';
				update(1,0,n,0,lst[a[j]]-1,j-lst[a[j]]);
//				cout<<get(1,0,n,0,lst[a[j]]-1)<<'\n';
			}
			lst[a[j]]=j;
			dp[j]=get(1,0,n,0,j-1);
		}
//		cout<<'\n';
	}
	cout<<dp[n]<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	t=1;
	while(t--)solve();
	RE 0;
}


```