#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define ppi pair<pii,int>
#define pip pair<int,pii>
#define ppp pair<pii,pii>
#define pdd pair<double, double>
#define f first
#define s second
#define MOD 1000000007
#define mkp make_pair
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define LOR(i,l,r) for (ll i=l;i<=r;i++)
#define FORD(i,r,l) for (int i=r;i>=l;i--)
#define LORD(i,r,l) for (ll i=r;i>=l;i--)
#define CL(x) memset(x,0,sizeof(x))
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x.size())
#define UI(x) (int)(x-'A')
#define LI(x) (int)(x-'a')
#define DI(x) (int)(x-'0')
#define LL_MAX (1LL<<60)
#define DB 0
#define DBG(x) if(DB)cout << #x << " : " << x << '\n'
#define PRALL(v) if(DB)for(auto it : v)cout<<v<<' '; NL;
#define NL cout<<'\n';
#define FND(S,x) (S.find(x)!=S.end())
#define bit(x,y) (!!(((ll)x)&(1LL<<y)))
typedef long long ll;
typedef long double ld;

#define MXN 38005
int N, K;
int A[MXN];
int lst[MXN], L[MXN];
ll DP[MXN][105];
int rnd;

//range min, range add
struct
{
    ll Get(int id){ return st[id]+ad[id]; }
    void up(int id)
    {
        st[id] = min(Get(id*2),Get(id*2+1));
    }
    void down(int l, int r, int id)
    {
        ll val = ad[id];
        ad[id] = 0;
        st[id] += val;
        if(l==r)return;
        ad[id*2]+=val, ad[id*2+1]+=val;
    }
    void build(int l, int r, int id)
    {
        ad[id] = 0;
        if(l==r)
        {
            st[id]=DP[l][rnd-1];
            return;
        }
        int m = (l+r)/2;
        build(l,m,id*2);
        build(m+1,r,id*2+1);
        up(id);
    }
    ll Min(int L, int R, int l, int r, int id)
    {
        down(l,r,id);
        if( l>=L && r<=R )return st[id];
        if( l>R || r<L )return LL_MAX;
        int m = (l+r)/2;
        return min(Min(L,R,l,m,id*2),Min(L,R,m+1,r,id*2+1));
    }
    void Add(int L, int R, ll x, int l, int r, int id)
    {
        down(l,r,id);
        if( l>=L && r<=R )
        {
            ad[id]+=x;
            return;
        }
        if( l>R || r<L )return;

        int m = (l+r)/2;
        Add(L,R,x,l,m,id*2);
        Add(L,R,x,m+1,r,id*2+1);
        up(id);
    }
    ll st[MXN*4], ad[MXN*4];
}segt;

void ini()
{
    cin>>N>>K;
    FOR(i,1,N)
    {
        cin>>A[i];
        L[i]=lst[ A[i] ];
        lst[ A[i] ]=i;
    }
}

void sol()
{
    //k=1
    FOR(i,1,N)
    {
        DP[i][1]=DP[i-1][1];
        if(L[i])DP[i][1]+=(i-L[i]);
    }
    FOR(k,2,K)
    {
        rnd = k;
        segt.build(1,N,1);
        FOR(i,1,N)
        {
            if( L[i] )
            {
                segt.Add( 1, L[i]-1, i-L[i], 1, N, 1 );
            }
            DP[i][k] = segt.Min( 1, N, 1, N, 1 );
        }
    }
    cout<<DP[N][K]<<'\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ini();
    sol();

    return 0;
}

### Prompt

Create a solution in Cpp for 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;
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define ppi pair<pii,int>
#define pip pair<int,pii>
#define ppp pair<pii,pii>
#define pdd pair<double, double>
#define f first
#define s second
#define MOD 1000000007
#define mkp make_pair
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define LOR(i,l,r) for (ll i=l;i<=r;i++)
#define FORD(i,r,l) for (int i=r;i>=l;i--)
#define LORD(i,r,l) for (ll i=r;i>=l;i--)
#define CL(x) memset(x,0,sizeof(x))
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x.size())
#define UI(x) (int)(x-'A')
#define LI(x) (int)(x-'a')
#define DI(x) (int)(x-'0')
#define LL_MAX (1LL<<60)
#define DB 0
#define DBG(x) if(DB)cout << #x << " : " << x << '\n'
#define PRALL(v) if(DB)for(auto it : v)cout<<v<<' '; NL;
#define NL cout<<'\n';
#define FND(S,x) (S.find(x)!=S.end())
#define bit(x,y) (!!(((ll)x)&(1LL<<y)))
typedef long long ll;
typedef long double ld;

#define MXN 38005
int N, K;
int A[MXN];
int lst[MXN], L[MXN];
ll DP[MXN][105];
int rnd;

//range min, range add
struct
{
    ll Get(int id){ return st[id]+ad[id]; }
    void up(int id)
    {
        st[id] = min(Get(id*2),Get(id*2+1));
    }
    void down(int l, int r, int id)
    {
        ll val = ad[id];
        ad[id] = 0;
        st[id] += val;
        if(l==r)return;
        ad[id*2]+=val, ad[id*2+1]+=val;
    }
    void build(int l, int r, int id)
    {
        ad[id] = 0;
        if(l==r)
        {
            st[id]=DP[l][rnd-1];
            return;
        }
        int m = (l+r)/2;
        build(l,m,id*2);
        build(m+1,r,id*2+1);
        up(id);
    }
    ll Min(int L, int R, int l, int r, int id)
    {
        down(l,r,id);
        if( l>=L && r<=R )return st[id];
        if( l>R || r<L )return LL_MAX;
        int m = (l+r)/2;
        return min(Min(L,R,l,m,id*2),Min(L,R,m+1,r,id*2+1));
    }
    void Add(int L, int R, ll x, int l, int r, int id)
    {
        down(l,r,id);
        if( l>=L && r<=R )
        {
            ad[id]+=x;
            return;
        }
        if( l>R || r<L )return;

        int m = (l+r)/2;
        Add(L,R,x,l,m,id*2);
        Add(L,R,x,m+1,r,id*2+1);
        up(id);
    }
    ll st[MXN*4], ad[MXN*4];
}segt;

void ini()
{
    cin>>N>>K;
    FOR(i,1,N)
    {
        cin>>A[i];
        L[i]=lst[ A[i] ];
        lst[ A[i] ]=i;
    }
}

void sol()
{
    //k=1
    FOR(i,1,N)
    {
        DP[i][1]=DP[i-1][1];
        if(L[i])DP[i][1]+=(i-L[i]);
    }
    FOR(k,2,K)
    {
        rnd = k;
        segt.build(1,N,1);
        FOR(i,1,N)
        {
            if( L[i] )
            {
                segt.Add( 1, L[i]-1, i-L[i], 1, N, 1 );
            }
            DP[i][k] = segt.Min( 1, N, 1, N, 1 );
        }
    }
    cout<<DP[N][K]<<'\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ini();
    sol();

    return 0;
}

```