#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 35000+5, K = 103, inf = INT_MAX/4;
int n, k, a[MAXN], lst[MAXN], li[MAXN], seg[MAXN*4][K], dp[MAXN][K], lazy[MAXN*4][K];
int s = 0;

inline void upd(int ind, int id){
	if(lazy[ind][id]!=-1){
		seg[ind*2][id] +=  lazy[ind][id];
		seg[ind*2+1][id] +=  lazy[ind][id];
		lazy[ind*2][id] += lazy[ind][id] + (lazy[ind*2][id]==-1);
		lazy[ind*2+1][id] += lazy[ind][id] + (lazy[ind*2+1][id]==-1);
		lazy[ind][id] = -1;
	}
	return;
}

int get(int id, int l, int r, int b = 0, int e = n, int ind = 1){
	if(r <= b || e <= l) return inf;
	if(l <= b && r >= e) return seg[ind][id];
	upd(ind, id);
	int mid = (b + e) / 2, ret = inf;
	if(l < mid) ret = min(ret, get(id, l, r, b, mid, ind * 2));
	if(r > mid) ret = min(ret, get(id, l, r, mid, e, ind * 2 + 1));
	seg[ind][id] = min(seg[ind*2][id], seg[ind*2+1][id]);
	return ret;
}

void add(int val, int id, int l, int r, int b = 0, int e = n, int ind = 1){
	if(l <= b && r >= e){
		seg[ind][id] += val;
		lazy[ind][id] = (lazy[ind][id]==-1?val:lazy[ind][id]+val);
//		cout << "l:" << l+1 << "  r:" << r << "  b:" << b+1 << "  e:" << e << "  seg:" << seg[ind][id] << endl;
		return;
	}
	upd(ind, id);
	int mid = (b + e) / 2;
	if(l < mid) add(val, id, l, r, b, mid, ind * 2);
	if(r > mid) add(val, id, l, r, mid, e, ind * 2 + 1);
	seg[ind][id] = min(seg[ind*2][id], seg[ind*2+1][id]);
//	cout << "l:" << l+1 << "  r:" << r << "  b:" << b+1 << "  e:" << e << "  seg:" << seg[ind][id] << endl;
	return;
}

void setto(int x, int val, int id, int b = 0, int e = n, int ind = 1){
	if(b + 1 == e){
		seg[ind][id] = val;
		return;
	}
	upd(ind, id);
	int mid = (b + e) / 2;
	if(x < mid) setto(x, val, id, b, mid, ind * 2);
	else setto(x, val, id, mid, e, ind * 2 + 1);
	seg[ind][id] = min(seg[ind*2][id], seg[ind*2+1][id]);
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	for(int i = 0; i < MAXN*4; i++) for(int j = 0; j < K; j++) seg[i][j] = inf, lazy[i][j] = -1;
	cin >> n >> k;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++){
		li[i] = lst[a[i]]-1;
		lst[a[i]] = i+1;
	}
	for(int i = 0; i < n; i++){
		s += (li[i]==-1?0:i-li[i]);
		dp[i][0] = s;
		setto(i, s, 0);// seg[i][0] = s
	}
	for(int j = 1; j < k; j++){
		dp[j][j] = 0;
		setto(j, 0, j); // seg[j][j] = 0
		for(int i = j+1; i < n; i++){
			if(li[i]>0){
				int x = i-li[i];
				//cout << "i:" << i+1 << "  j:" << j+1 << "  x:" << x << "  r:" << li[i] << endl;
//				cout << "add: +" << x << " - " << li[i] << "  i:" << i+1 << endl;
				add(x, j-1, 0, li[i]); //seg[0-li[i]-1][j] += x
			}
			dp[i][j] = get(j-1,0,i);
			setto(i, dp[i][j], j); // seg[i][j] = dp[i][j]
		}
	}
/*	for(int j = 0; j < k; j++){
		cout << "j+1:" << j << ":   ";
		for(int i = 0; i < n; i++) cout << dp[i][j] << " ";
		cout << endl;
	}*/
	cout << dp[n-1][k-1] << '\n';
	return 0; 
}

### Prompt

Please create a solution in cpp 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>

using namespace std;
typedef long long int ll;

const int MAXN = 35000+5, K = 103, inf = INT_MAX/4;
int n, k, a[MAXN], lst[MAXN], li[MAXN], seg[MAXN*4][K], dp[MAXN][K], lazy[MAXN*4][K];
int s = 0;

inline void upd(int ind, int id){
	if(lazy[ind][id]!=-1){
		seg[ind*2][id] +=  lazy[ind][id];
		seg[ind*2+1][id] +=  lazy[ind][id];
		lazy[ind*2][id] += lazy[ind][id] + (lazy[ind*2][id]==-1);
		lazy[ind*2+1][id] += lazy[ind][id] + (lazy[ind*2+1][id]==-1);
		lazy[ind][id] = -1;
	}
	return;
}

int get(int id, int l, int r, int b = 0, int e = n, int ind = 1){
	if(r <= b || e <= l) return inf;
	if(l <= b && r >= e) return seg[ind][id];
	upd(ind, id);
	int mid = (b + e) / 2, ret = inf;
	if(l < mid) ret = min(ret, get(id, l, r, b, mid, ind * 2));
	if(r > mid) ret = min(ret, get(id, l, r, mid, e, ind * 2 + 1));
	seg[ind][id] = min(seg[ind*2][id], seg[ind*2+1][id]);
	return ret;
}

void add(int val, int id, int l, int r, int b = 0, int e = n, int ind = 1){
	if(l <= b && r >= e){
		seg[ind][id] += val;
		lazy[ind][id] = (lazy[ind][id]==-1?val:lazy[ind][id]+val);
//		cout << "l:" << l+1 << "  r:" << r << "  b:" << b+1 << "  e:" << e << "  seg:" << seg[ind][id] << endl;
		return;
	}
	upd(ind, id);
	int mid = (b + e) / 2;
	if(l < mid) add(val, id, l, r, b, mid, ind * 2);
	if(r > mid) add(val, id, l, r, mid, e, ind * 2 + 1);
	seg[ind][id] = min(seg[ind*2][id], seg[ind*2+1][id]);
//	cout << "l:" << l+1 << "  r:" << r << "  b:" << b+1 << "  e:" << e << "  seg:" << seg[ind][id] << endl;
	return;
}

void setto(int x, int val, int id, int b = 0, int e = n, int ind = 1){
	if(b + 1 == e){
		seg[ind][id] = val;
		return;
	}
	upd(ind, id);
	int mid = (b + e) / 2;
	if(x < mid) setto(x, val, id, b, mid, ind * 2);
	else setto(x, val, id, mid, e, ind * 2 + 1);
	seg[ind][id] = min(seg[ind*2][id], seg[ind*2+1][id]);
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	for(int i = 0; i < MAXN*4; i++) for(int j = 0; j < K; j++) seg[i][j] = inf, lazy[i][j] = -1;
	cin >> n >> k;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++){
		li[i] = lst[a[i]]-1;
		lst[a[i]] = i+1;
	}
	for(int i = 0; i < n; i++){
		s += (li[i]==-1?0:i-li[i]);
		dp[i][0] = s;
		setto(i, s, 0);// seg[i][0] = s
	}
	for(int j = 1; j < k; j++){
		dp[j][j] = 0;
		setto(j, 0, j); // seg[j][j] = 0
		for(int i = j+1; i < n; i++){
			if(li[i]>0){
				int x = i-li[i];
				//cout << "i:" << i+1 << "  j:" << j+1 << "  x:" << x << "  r:" << li[i] << endl;
//				cout << "add: +" << x << " - " << li[i] << "  i:" << i+1 << endl;
				add(x, j-1, 0, li[i]); //seg[0-li[i]-1][j] += x
			}
			dp[i][j] = get(j-1,0,i);
			setto(i, dp[i][j], j); // seg[i][j] = dp[i][j]
		}
	}
/*	for(int j = 0; j < k; j++){
		cout << "j+1:" << j << ":   ";
		for(int i = 0; i < n; i++) cout << dp[i][j] << " ";
		cout << endl;
	}*/
	cout << dp[n-1][k-1] << '\n';
	return 0; 
}

```