#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef double db;
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define low(x) ((x)&-(x))
#define all(x) x.begin(),x.end()
#define mp make_pair
#define X first
#define Y second
#ifdef _DEBUG
    const int N=1e3+10;
#else
    const int N=1e6+10;
#endif
const ll mod=1e9+7;
inline ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
inline ll q_pow(ll a,ll x){ll ans=1,tmp=a;while(x){if(x&1)(ans*=tmp)%=mod;(tmp*=tmp)%=mod;x>>=1;}return ans;}
template<typename T> inline void re(T &N){int f=1;char c;while((c=getchar())< '0'||c> '9')if(c=='-')f=-1;N=c-'0';while((c=getchar())>='0'&&c<='9')N=N*10+c-'0';N*=f;}
int m,n,t=1,st,en;
int a[N],b[N];
struct SegT{
    int e[N<<2],tag[N<<2];
    
    inline void push_up(int p)
    {
        e[p]=min(e[ls(p)],e[rs(p)]);
    }
    void build(int p,int l,int r)
    {
        e[p]=1e9;tag[p]=0;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(ls(p),l,mid);
        build(rs(p),mid+1,r); 
    }
    inline void push_down(int p)
    {
        if(tag[p])
        {
            e[ls(p)]+=tag[p];tag[ls(p)]+=tag[p];
            e[rs(p)]+=tag[p];tag[rs(p)]+=tag[p];
            tag[p]=0;
        }
    }
    int query(){return e[1];}
    int query(int p,int l,int r,int L,int R)
    {
        int ans=1e9;
        if(L<=l&&r<=R)return e[p];
        int mid=(l+r)>>1;
        push_down(p);
        if(L<=mid)ans=min(ans,query(ls(p),l,mid,L,R));
        if(mid< R)ans=min(ans,query(rs(p),mid+1,r,L,R));
        return ans;
    }
    void update1(int p,int l,int r,int L,int R,int k)
    {
        if(L<=l&&r<=R)return e[p]=k,void();
        int mid=(l+r)>>1;
        push_down(p);
        if(L<=mid)update1(ls(p),l,mid,L,R,k);
        if(mid< R)update1(rs(p),mid+1,r,L,R,k);
        push_up(p);
    }
    void update2(int p,int l,int r,int L,int R,int k)
    {
        if(L<=l&&r<=R)
        {
            e[p]+=k;tag[p]+=k;
            return;
        }
        int mid=(l+r)>>1;
        push_down(p);
        if(L<=mid)update2(ls(p),l,mid,L,R,k);
        if(mid< R)update2(rs(p),mid+1,r,L,R,k);
        push_up(p);
    }
}tr;
int d[N],la[N];

int main()
{
    #ifdef _DEBUG
        freopen("data.txt","r",stdin);
    #endif
    re(n);re(m);
    for(int i=1;i<=n;i++)re(a[i]);
    fill(d,d+n+1,1e9);d[0]=0;
    for(int j=1;j<=m;j++)
    {
        tr.build(1,1,n+1);
        tr.update1(1,1,n+1,1,1,0);
        fill(la+1,la+n+1,0);
        for(int i=1;i<=n;i++)
        {
            tr.update1(1,1,n+1,i+1,i+1,d[i]);
            if(la[a[i]])
            {
                tr.update2(1,1,n+1,1,la[a[i]]-1+1,i-la[a[i]]);
            }
            d[i]=tr.query();
            la[a[i]]=i;
        }
    }
    printf("%d\n",d[n]);
}

### Prompt

Develop a solution in cpp to the problem described below:

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 ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef double db;
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define low(x) ((x)&-(x))
#define all(x) x.begin(),x.end()
#define mp make_pair
#define X first
#define Y second
#ifdef _DEBUG
    const int N=1e3+10;
#else
    const int N=1e6+10;
#endif
const ll mod=1e9+7;
inline ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
inline ll q_pow(ll a,ll x){ll ans=1,tmp=a;while(x){if(x&1)(ans*=tmp)%=mod;(tmp*=tmp)%=mod;x>>=1;}return ans;}
template<typename T> inline void re(T &N){int f=1;char c;while((c=getchar())< '0'||c> '9')if(c=='-')f=-1;N=c-'0';while((c=getchar())>='0'&&c<='9')N=N*10+c-'0';N*=f;}
int m,n,t=1,st,en;
int a[N],b[N];
struct SegT{
    int e[N<<2],tag[N<<2];
    
    inline void push_up(int p)
    {
        e[p]=min(e[ls(p)],e[rs(p)]);
    }
    void build(int p,int l,int r)
    {
        e[p]=1e9;tag[p]=0;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(ls(p),l,mid);
        build(rs(p),mid+1,r); 
    }
    inline void push_down(int p)
    {
        if(tag[p])
        {
            e[ls(p)]+=tag[p];tag[ls(p)]+=tag[p];
            e[rs(p)]+=tag[p];tag[rs(p)]+=tag[p];
            tag[p]=0;
        }
    }
    int query(){return e[1];}
    int query(int p,int l,int r,int L,int R)
    {
        int ans=1e9;
        if(L<=l&&r<=R)return e[p];
        int mid=(l+r)>>1;
        push_down(p);
        if(L<=mid)ans=min(ans,query(ls(p),l,mid,L,R));
        if(mid< R)ans=min(ans,query(rs(p),mid+1,r,L,R));
        return ans;
    }
    void update1(int p,int l,int r,int L,int R,int k)
    {
        if(L<=l&&r<=R)return e[p]=k,void();
        int mid=(l+r)>>1;
        push_down(p);
        if(L<=mid)update1(ls(p),l,mid,L,R,k);
        if(mid< R)update1(rs(p),mid+1,r,L,R,k);
        push_up(p);
    }
    void update2(int p,int l,int r,int L,int R,int k)
    {
        if(L<=l&&r<=R)
        {
            e[p]+=k;tag[p]+=k;
            return;
        }
        int mid=(l+r)>>1;
        push_down(p);
        if(L<=mid)update2(ls(p),l,mid,L,R,k);
        if(mid< R)update2(rs(p),mid+1,r,L,R,k);
        push_up(p);
    }
}tr;
int d[N],la[N];

int main()
{
    #ifdef _DEBUG
        freopen("data.txt","r",stdin);
    #endif
    re(n);re(m);
    for(int i=1;i<=n;i++)re(a[i]);
    fill(d,d+n+1,1e9);d[0]=0;
    for(int j=1;j<=m;j++)
    {
        tr.build(1,1,n+1);
        tr.update1(1,1,n+1,1,1,0);
        fill(la+1,la+n+1,0);
        for(int i=1;i<=n;i++)
        {
            tr.update1(1,1,n+1,i+1,i+1,d[i]);
            if(la[a[i]])
            {
                tr.update2(1,1,n+1,1,la[a[i]]-1+1,i-la[a[i]]);
            }
            d[i]=tr.query();
            la[a[i]]=i;
        }
    }
    printf("%d\n",d[n]);
}

```