#include <bits/stdc++.h>
#define ll long long int
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define fori(i,n) for(ll i=0;i<n;i++)
#define pb push_back
#define mod 998244353
#define pi pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
#define debug(x) cout<<#x<<" = "<<x<<endl
#define printVector(v) fori(i,v.size()) {cout << v[i] << " ";} cout << "\n";
using namespace std;
struct segtree
{
	int treesize;
	vector <ll> values;
	vector<ll> operations;
	ll IDENTITY_ELEMENT=LLONG_MAX;    ///Identity for calc operation
	ll NO_OPERATION =   0;		//No operation for modify op
	void build(int x,int l,int r,vector<ll> &a)
	{
		if(l==r)								//be careful l can be out of bound of vector you are assigning values from
		{
			if(l < a.size())
			values[x] = a[l];  //change to required values in build and dont forget to build if required,its not included in init
			return;
		}
		int mid = (l+r)/2;
		build(2*x+1,l,mid,a);
		build(2*x+2,mid+1,r,a);
		values[x] = calc_op(values[2*x+1],values[2*x+2]);
	}
	void init(int n)			//Allocate space and initialize values for seg tree
	{							//included in build function

		treesize=1;
		while(treesize < n){treesize *=2;}
		operations.assign(2*treesize,NO_OPERATION);				//Initial state values dont forget to change
		values.assign(2*treesize,IDENTITY_ELEMENT);
	}

	/////////////////////////////////MASS OPERATIONS/////////////////////////////////////////////
	inline ll modify_op(ll a, ll b,ll len)
	{
		return a + b;
	}

	inline ll calc_op(ll a , ll b)
	{
		return min(a,b);
	}
	inline void apply_modify_op(ll &a,ll b,ll len)
	{
		a = modify_op(a,b,len);
	}

	inline void propagate(int x,int l,int r)
	{
		if(x >= treesize-1) return;
		int mid = (l+r)/2;
		apply_modify_op(operations[2*x+1],operations[x],1);
		apply_modify_op(operations[2*x+2],operations[x],1);
		apply_modify_op(values[2*x+1],operations[x],mid-l+1);
		apply_modify_op(values[2*x+2],operations[x],r-mid);
		operations[x] = NO_OPERATION;
	}
	void modify(ll val,int ql,int qr,int curr,int l,int r)
	{
		propagate(curr,l,r);
		if(l > qr || ql > r){return;}
		if(l >= ql  && r <= qr)
		{
			apply_modify_op(operations[curr],val,1);
			apply_modify_op(values[curr],val,r-l+1);
			return;
		}
		int mid = (l+r)/2;
		modify(val,ql,qr,2*curr+1,l,mid);
		modify(val,ql,qr,2*curr+2,mid+1,r);
		values[curr] = calc_op(values[2*curr+1],values[2*curr+2]) ;
	}
	void modify(ll val,int ql,int qr)
	{
		modify(val,ql,qr,0,0,treesize-1);
	}
	ll calc(int ql,int qr,int curr,int l,int r)
	{
		propagate(curr,l,r);
		if(l > qr || ql > r){return IDENTITY_ELEMENT;}
		if(l >= ql  && r <= qr)
		{
			return values[curr];

		}
		int mid = (l+r)/2;
		ll m1 = calc(ql,qr,2*curr+1,l,mid);
		ll m2 = calc(ql,qr,2*curr+2,mid+1,r);
		ll res = calc_op(m1,m2);
		return res;
	}
	ll calc(int ql,int qr)
	{
		return calc(ql,qr,0,0,treesize-1);
	}

};
void solve()
{
	int n,k;
	cin >> n >> k;
	vector<ll> a(n);
	fori(i,n) {cin >> a[i];a[i]--;}
	segtree st;
	vector<int> latestSeen(n,-1);
	ll curAns = 0;
	st.init(n+1);
	vector<ll > initVal(n+1,0);
	fori(i,n)
	{
		if(latestSeen[a[i]]!= -1)
		{
			curAns += i - latestSeen[a[i]];
			latestSeen[a[i]] = i;
		}
		else
		{
			latestSeen[a[i]] = i;
		}
		initVal[i+1] = curAns;
	}
	st.build(0,0,st.treesize-1,initVal);
	vector<ll> tmp(n+1);
	for(int i = 1; i < k; i++)
	{
		latestSeen.assign(n,-1);
		tmp[0] = 0;
		for(int j = 1; j <= n; j++)
		{
			if(latestSeen[a[j-1]]==-1)
			{
				latestSeen[a[j-1]] = j-1;
			}
			else
			{
				st.modify((ll)(j-1) - latestSeen[a[j-1]],0,latestSeen[a[j-1]]);
				latestSeen[a[j-1]] = j-1;
			}
            ll res = st.values[0];
            tmp[j] = res;
		}
		st.operations.assign(st.operations.size(),st.NO_OPERATION);
		st.build(0,0,st.treesize-1,tmp);

	}
	cout << st.calc(n,n) << "\n";

}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ttt=1;
    //cin >> ttt;
    while(ttt--) solve();
}

### Prompt

Your challenge is to write 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 <bits/stdc++.h>
#define ll long long int
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define fori(i,n) for(ll i=0;i<n;i++)
#define pb push_back
#define mod 998244353
#define pi pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
#define debug(x) cout<<#x<<" = "<<x<<endl
#define printVector(v) fori(i,v.size()) {cout << v[i] << " ";} cout << "\n";
using namespace std;
struct segtree
{
	int treesize;
	vector <ll> values;
	vector<ll> operations;
	ll IDENTITY_ELEMENT=LLONG_MAX;    ///Identity for calc operation
	ll NO_OPERATION =   0;		//No operation for modify op
	void build(int x,int l,int r,vector<ll> &a)
	{
		if(l==r)								//be careful l can be out of bound of vector you are assigning values from
		{
			if(l < a.size())
			values[x] = a[l];  //change to required values in build and dont forget to build if required,its not included in init
			return;
		}
		int mid = (l+r)/2;
		build(2*x+1,l,mid,a);
		build(2*x+2,mid+1,r,a);
		values[x] = calc_op(values[2*x+1],values[2*x+2]);
	}
	void init(int n)			//Allocate space and initialize values for seg tree
	{							//included in build function

		treesize=1;
		while(treesize < n){treesize *=2;}
		operations.assign(2*treesize,NO_OPERATION);				//Initial state values dont forget to change
		values.assign(2*treesize,IDENTITY_ELEMENT);
	}

	/////////////////////////////////MASS OPERATIONS/////////////////////////////////////////////
	inline ll modify_op(ll a, ll b,ll len)
	{
		return a + b;
	}

	inline ll calc_op(ll a , ll b)
	{
		return min(a,b);
	}
	inline void apply_modify_op(ll &a,ll b,ll len)
	{
		a = modify_op(a,b,len);
	}

	inline void propagate(int x,int l,int r)
	{
		if(x >= treesize-1) return;
		int mid = (l+r)/2;
		apply_modify_op(operations[2*x+1],operations[x],1);
		apply_modify_op(operations[2*x+2],operations[x],1);
		apply_modify_op(values[2*x+1],operations[x],mid-l+1);
		apply_modify_op(values[2*x+2],operations[x],r-mid);
		operations[x] = NO_OPERATION;
	}
	void modify(ll val,int ql,int qr,int curr,int l,int r)
	{
		propagate(curr,l,r);
		if(l > qr || ql > r){return;}
		if(l >= ql  && r <= qr)
		{
			apply_modify_op(operations[curr],val,1);
			apply_modify_op(values[curr],val,r-l+1);
			return;
		}
		int mid = (l+r)/2;
		modify(val,ql,qr,2*curr+1,l,mid);
		modify(val,ql,qr,2*curr+2,mid+1,r);
		values[curr] = calc_op(values[2*curr+1],values[2*curr+2]) ;
	}
	void modify(ll val,int ql,int qr)
	{
		modify(val,ql,qr,0,0,treesize-1);
	}
	ll calc(int ql,int qr,int curr,int l,int r)
	{
		propagate(curr,l,r);
		if(l > qr || ql > r){return IDENTITY_ELEMENT;}
		if(l >= ql  && r <= qr)
		{
			return values[curr];

		}
		int mid = (l+r)/2;
		ll m1 = calc(ql,qr,2*curr+1,l,mid);
		ll m2 = calc(ql,qr,2*curr+2,mid+1,r);
		ll res = calc_op(m1,m2);
		return res;
	}
	ll calc(int ql,int qr)
	{
		return calc(ql,qr,0,0,treesize-1);
	}

};
void solve()
{
	int n,k;
	cin >> n >> k;
	vector<ll> a(n);
	fori(i,n) {cin >> a[i];a[i]--;}
	segtree st;
	vector<int> latestSeen(n,-1);
	ll curAns = 0;
	st.init(n+1);
	vector<ll > initVal(n+1,0);
	fori(i,n)
	{
		if(latestSeen[a[i]]!= -1)
		{
			curAns += i - latestSeen[a[i]];
			latestSeen[a[i]] = i;
		}
		else
		{
			latestSeen[a[i]] = i;
		}
		initVal[i+1] = curAns;
	}
	st.build(0,0,st.treesize-1,initVal);
	vector<ll> tmp(n+1);
	for(int i = 1; i < k; i++)
	{
		latestSeen.assign(n,-1);
		tmp[0] = 0;
		for(int j = 1; j <= n; j++)
		{
			if(latestSeen[a[j-1]]==-1)
			{
				latestSeen[a[j-1]] = j-1;
			}
			else
			{
				st.modify((ll)(j-1) - latestSeen[a[j-1]],0,latestSeen[a[j-1]]);
				latestSeen[a[j-1]] = j-1;
			}
            ll res = st.values[0];
            tmp[j] = res;
		}
		st.operations.assign(st.operations.size(),st.NO_OPERATION);
		st.build(0,0,st.treesize-1,tmp);

	}
	cout << st.calc(n,n) << "\n";

}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ttt=1;
    //cin >> ttt;
    while(ttt--) solve();
}

```