			#include <iostream>
        #include <cstring>
        #include <vector>
        #include <set>
        #include <bits/stdc++.h>
        #include <stdlib.h>
        #include <math.h>
        #include <queue>
        #include <iomanip>
        #include <tuple>
        #define MOD 998244353
        #include <chrono>
        #define boost ios_base::sync_with_stdio(false); cin.tie(NULL);
		#define int long long
		#define YES cout<<"YES"<<endl;
		#define NO cout<<"NO"<<endl;
		#define nw cout<<endl;
		#define zero(a) memset(a,0,sizeof(a));
		#define all(a) (a).begin(),(a).end();
		#define one(a) memset(a,1,sizeof(a));
		#define sz(a) (int) a.size();
        using namespace std;
        using namespace std::chrono;
        
  int mul(int a,int b)
  {
	  return (a*b)%MOD;
  }
  
  int modinv(int a)
  {
	  int b=MOD-2;
	  int A=a;
	  int c=1;
	  for(int i=0;i<62;i++)
	  {
		  if((long long)1<<i&(b))
		  {
			  c=mul(c,A);
		  }
		  A*=A;
		  A%=MOD;
	  }
	  return c;
  }
  
  
  int mul(int a,int b,int c)
  {
	  return mul(mul(a,b),c);
  }   
  
  int input(vector<char> &A)  
  {
	  string s;
	  cin>>s;
	  vector<char> B(s.begin(),s.end());
	  A=B;
	  return 0;
  }
  
int nCr(int n,int r)
{
	int num=1;
	int den=1;
	int k=max(r,n-r);
	for(int i=k+1;i<=n;i++)
	{
		num=mul(num,i);
	}
	for(int i=1;i<=n-k;i++)
	{
		den=mul(den,i);
	}
	return mul(num,modinv(den));
}
		
  
int count(int nums)
{
	int val=0;
	int k=nums;
	while(k!=0)
	{
		k=(long long)k&(k-1);
		val++;
	}

	return val;
}

vector<int> Tree;
vector<int> Lazy;

int n;

int makeTree(vector<int> &A,int l,int r,int v)
{
	if(l>r)
	{
		return 0;
	}
	else if(l==r)
	{
		Tree[v]=A[l];
		return 0;
		
	}
	else
	{
		int mid=(l+r)>>1;
		makeTree(A,l,mid,2*v);
		makeTree(A,mid+1,r,2*v+1);
		Tree[v]=min(Tree[2*v],Tree[2*v+1]);
		return 0;
	}
}

int update(int l,int r,int L,int R,int v,int val)
{
	if(l>r||L>R||l>R||L>r)
	{
		return 0;
	}
	else if(l==L&&r==R)
	{
		Lazy[v]+=val;
		return 0;
	}
	else
	{
		int mid=(L+R)>>1;
		update(l,min(mid,r),L,mid,2*v,val);
		update((max(mid+1,l)),r,mid+1,R,2*v+1,val);
		Tree[v]=min(Tree[2*v]+Lazy[2*v],Tree[2*v+1]+Lazy[2*v+1]);
		return 0;
	}
}

int query(int l,int r,int L,int R,int v)
{
	if(l>r||L>R||l>R||L>r)
	{
		return 1e15;
	}
	else if(l==L&&r==R)
	{
		return Tree[v]+Lazy[v];
	}
	else
	{
		int mid=(L+R)>>1;
		return min(query(l,min(mid,r),L,mid,2*v),query((max(mid+1,l)),r,mid+1,R,2*v+1));
	}
}
		
 
    
int32_t main()
{
    boost
    int T;
  T=1;
 
    while(T--)
    {
		
		int k;
		cin>>n>>k;
		vector<int> A(n+1,0);
		for(int i=0;i<n;i++)
		{
			cin>>A[i+1];
		}
		Tree.assign(4*n+1,0);
		Lazy.assign(4*n+1,0);
		vector<int> prev(n+1,0);
		map<int,int> Prev;
		for(int i=1;i<n+1;i++)
		{
			//cout<<i<<"GGWGW"<<endl;
			if(Prev.find(A[i])==Prev.end())
			{
				Prev[A[i]]=i;
			}
			else
			{
				prev[i]=Prev[A[i]];
				Prev[A[i]]=i;
			}
		}
		
		vector<vector<int>> dp;
		dp.resize(k+1);
		for(int i=0;i<k+1;i++)
		{
			dp[i].assign(n+1,1e15);
		}
	
		dp[1][0]=0;
		for(int i=1;i<n+1;i++)
		{
			dp[1][i]=dp[1][i-1];
			if(prev[i]!=0)
			{
				dp[1][i]+=i;
				dp[1][i]-=prev[i];
			}
			//cout<<i<<"GAA"<<" "<<dp[1][i]<<" "<<i<<" "<<prev[i]<<" "<<dp[1][i-1]<<endl;
		}
		
		for(int j=2;j<k+1;j++)
		{
				Tree.assign(4*n+1,0);
				Lazy.assign(4*n+1,0);
				makeTree(dp[j-1],1,n,1);
				for(int i=1;i<n+1;i++)
				{
					
					if(prev[i]!=0)
					{
						update(1,prev[i]-1,1,n,1,i-prev[i]);
					}
					dp[j][i]=query(1,i,1,n,1);
					
					
				}
		}
		
		cout<<dp[k][n]<<endl;
		
		
		
			
		
	}
	
    return 0;
}

### 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 <iostream>
        #include <cstring>
        #include <vector>
        #include <set>
        #include <bits/stdc++.h>
        #include <stdlib.h>
        #include <math.h>
        #include <queue>
        #include <iomanip>
        #include <tuple>
        #define MOD 998244353
        #include <chrono>
        #define boost ios_base::sync_with_stdio(false); cin.tie(NULL);
		#define int long long
		#define YES cout<<"YES"<<endl;
		#define NO cout<<"NO"<<endl;
		#define nw cout<<endl;
		#define zero(a) memset(a,0,sizeof(a));
		#define all(a) (a).begin(),(a).end();
		#define one(a) memset(a,1,sizeof(a));
		#define sz(a) (int) a.size();
        using namespace std;
        using namespace std::chrono;
        
  int mul(int a,int b)
  {
	  return (a*b)%MOD;
  }
  
  int modinv(int a)
  {
	  int b=MOD-2;
	  int A=a;
	  int c=1;
	  for(int i=0;i<62;i++)
	  {
		  if((long long)1<<i&(b))
		  {
			  c=mul(c,A);
		  }
		  A*=A;
		  A%=MOD;
	  }
	  return c;
  }
  
  
  int mul(int a,int b,int c)
  {
	  return mul(mul(a,b),c);
  }   
  
  int input(vector<char> &A)  
  {
	  string s;
	  cin>>s;
	  vector<char> B(s.begin(),s.end());
	  A=B;
	  return 0;
  }
  
int nCr(int n,int r)
{
	int num=1;
	int den=1;
	int k=max(r,n-r);
	for(int i=k+1;i<=n;i++)
	{
		num=mul(num,i);
	}
	for(int i=1;i<=n-k;i++)
	{
		den=mul(den,i);
	}
	return mul(num,modinv(den));
}
		
  
int count(int nums)
{
	int val=0;
	int k=nums;
	while(k!=0)
	{
		k=(long long)k&(k-1);
		val++;
	}

	return val;
}

vector<int> Tree;
vector<int> Lazy;

int n;

int makeTree(vector<int> &A,int l,int r,int v)
{
	if(l>r)
	{
		return 0;
	}
	else if(l==r)
	{
		Tree[v]=A[l];
		return 0;
		
	}
	else
	{
		int mid=(l+r)>>1;
		makeTree(A,l,mid,2*v);
		makeTree(A,mid+1,r,2*v+1);
		Tree[v]=min(Tree[2*v],Tree[2*v+1]);
		return 0;
	}
}

int update(int l,int r,int L,int R,int v,int val)
{
	if(l>r||L>R||l>R||L>r)
	{
		return 0;
	}
	else if(l==L&&r==R)
	{
		Lazy[v]+=val;
		return 0;
	}
	else
	{
		int mid=(L+R)>>1;
		update(l,min(mid,r),L,mid,2*v,val);
		update((max(mid+1,l)),r,mid+1,R,2*v+1,val);
		Tree[v]=min(Tree[2*v]+Lazy[2*v],Tree[2*v+1]+Lazy[2*v+1]);
		return 0;
	}
}

int query(int l,int r,int L,int R,int v)
{
	if(l>r||L>R||l>R||L>r)
	{
		return 1e15;
	}
	else if(l==L&&r==R)
	{
		return Tree[v]+Lazy[v];
	}
	else
	{
		int mid=(L+R)>>1;
		return min(query(l,min(mid,r),L,mid,2*v),query((max(mid+1,l)),r,mid+1,R,2*v+1));
	}
}
		
 
    
int32_t main()
{
    boost
    int T;
  T=1;
 
    while(T--)
    {
		
		int k;
		cin>>n>>k;
		vector<int> A(n+1,0);
		for(int i=0;i<n;i++)
		{
			cin>>A[i+1];
		}
		Tree.assign(4*n+1,0);
		Lazy.assign(4*n+1,0);
		vector<int> prev(n+1,0);
		map<int,int> Prev;
		for(int i=1;i<n+1;i++)
		{
			//cout<<i<<"GGWGW"<<endl;
			if(Prev.find(A[i])==Prev.end())
			{
				Prev[A[i]]=i;
			}
			else
			{
				prev[i]=Prev[A[i]];
				Prev[A[i]]=i;
			}
		}
		
		vector<vector<int>> dp;
		dp.resize(k+1);
		for(int i=0;i<k+1;i++)
		{
			dp[i].assign(n+1,1e15);
		}
	
		dp[1][0]=0;
		for(int i=1;i<n+1;i++)
		{
			dp[1][i]=dp[1][i-1];
			if(prev[i]!=0)
			{
				dp[1][i]+=i;
				dp[1][i]-=prev[i];
			}
			//cout<<i<<"GAA"<<" "<<dp[1][i]<<" "<<i<<" "<<prev[i]<<" "<<dp[1][i-1]<<endl;
		}
		
		for(int j=2;j<k+1;j++)
		{
				Tree.assign(4*n+1,0);
				Lazy.assign(4*n+1,0);
				makeTree(dp[j-1],1,n,1);
				for(int i=1;i<n+1;i++)
				{
					
					if(prev[i]!=0)
					{
						update(1,prev[i]-1,1,n,1,i-prev[i]);
					}
					dp[j][i]=query(1,i,1,n,1);
					
					
				}
		}
		
		cout<<dp[k][n]<<endl;
		
		
		
			
		
	}
	
    return 0;
}

```