#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define nl cout<<"\n"
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
// const ll MOD = 998244353;
template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD ){ x += y; if( x >= m ) x -= m; }
template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD ){ x -= y; if( x < 0 ) x += m; }
ll mod( ll n, ll m=MOD ){ n%=m;if(n<0)n+=m;return n; }

const int MAXN = 35005;
const int LOGN = 21;
const ll INF = 1e17;

template<class T>
class PersistentSeg
{
public:
    int NODES, N, root;
    vector<int> L, R;
    vector<T> tree;
    T IDENTITY;
    PersistentSeg(int n)
    {
        N = n+5;
        NODES = 0;
        IDENTITY = 0;
        int lg = 0;
        for(int i=1;i<N;i<<=1,lg++);
        L.resize(8*N*lg);
        R.resize(8*N*lg);
        tree.resize(8*N*lg);
        root = build(0,N-1);
    }
    int newleaf(T val)
    {
        int p = ++NODES;
        L[p] = R[p] = 0;
        tree[p] = val;
        return p;
    }
    T merge( T x, T y )
    {
        return x+y;
    }
    int newparent(int lid, int rid)
    {
        int p = ++NODES;
        L[p] = lid;
        R[p] = rid;
        tree[p] = merge( tree[lid], tree[rid] );
        return p;
    }
    int build(int l, int r)
    {
        if( l == r )
            return newleaf(IDENTITY);
        int m = l + (r-l)/2;
        return newparent(build(l, m), build(m+1, r));
    }
    int update(int pos, T val, int node, int l, int r)
    {
        if( l == r )
            return newleaf(val);
        int m = l + (r-l)/2;
        if( pos > m )
            return newparent(L[node], update(pos, val, R[node], m+1, r));
        else
            return newparent(update(pos, val, L[node], l, m), R[node]);
    }
    T query(int ql, int qr, int node, int l, int r)
    {
        if( ql > r || qr < l )
            return IDENTITY;
        if( ql <= l && r <= qr )
            return tree[node];
        int m = l + (r-l)/2;
        return merge( query(ql, qr, L[node], l, m), query(ql, qr, R[node], m+1, r) );
    }
    int update(int pos, int val, int root)
    {
        return update(pos, val, root, 0, N-1);
    }
    T query(int ql, int qr, int root)
    {
        return query(ql, qr, root, 0, N-1);
    }
};

PersistentSeg<ll> prefix(MAXN), suffix(MAXN);
vector<int> prefix_roots(MAXN), suffix_roots(MAXN), nxt(MAXN);
vector<ll> dp(MAXN, INF), ndp(MAXN, INF);
int n, k;

ll cost(int i, int j)
{
    // cout<<i<<" "<<j,nl;
    // return 0;
    if( i > j ) return 0;
    ll psum = ( ( 1 <= j && j <= n ) ? prefix.query(i,j,prefix_roots[j]) : 0 );
    ll ssum = ( ( 1 <= i && i <= n ) ? suffix.query(i,j,suffix_roots[i]) : 0 );
    return psum + ssum;
}

void compute(int l, int r, int optl, int optr)
{
    if( l > r )
        return;

    int mid = l + (r-l)/2;

    pair<ll,ll> best = {INF, mid};
    ll temp = cost(optr+1, mid);
    for(int k=min(mid, optr); k>=max(1,optl); k--)
    {
        if( nxt[k] <= mid )
            temp += ( nxt[k] - k );
        best = min( best, { ( k-1 >= 0 ? dp[k-1] : 0 ) + temp, k } );
    }

    ndp[mid] = best.first;
    int opt = best.second;

    compute(l,mid-1,optl,opt);
    compute(mid+1,r,opt,optr);
}


void solve()
{
    cin>>n>>k;

    vector<ll> a(n+5);

    for(int i=1;i<=n;i++)
        cin>>a[i];

    vector<int> prv(n+5,n+1);
    for(int i=n;i>=1;i--)
    {
        nxt[i] = prv[a[i]];
        prv[a[i]] = i;
    }

    prv.assign(n+5,-1);
    int st = prefix.root;
    prefix_roots[0] = st;
    for(int i=1;i<=n;i++)
    {
        int val = a[i];

        if( prv[val] != -1 )
            st = prefix.update(prv[val], 0, st);
        prv[val] = i;

        st = prefix.update(prv[val], i, st);
        prefix_roots[i] = st;


        // for(int j=1;j<=n;j++)
        // {
        //     cout<<prefix.query(j,j,st)<<" ";
        // }
        // nl;
    }

    prv.assign(n+5,-1);
    st = suffix.root;
    suffix_roots[n+1] = st;
    for(int i=n;i>=1;i--)
    {
        int val = a[i];

        if( prv[val] != -1 )
            st = suffix.update(prv[val], 0, st);
        prv[val] = i;

        st = suffix.update(prv[val], -i, st);
        suffix_roots[i] = st;

        // for(int j=1;j<=n;j++)
        // {
        //     cout<<suffix.query(j,j,st)<<" ";
        // }
        // nl;
    }

    // for( auto x : prefix_roots )
    //     cout<<x<<" ";
    // nl;

    // for( auto x : suffix_roots )
    //     cout<<x<<" ";
    // nl;

    // return;

    // auto brute = [&](int i, int j)
    // {
    //     vector<int> first(n+1,n), last(n+1,-1);
    //     for(int k=i;k<=j;k++)
    //     {
    //         min_self( first[a[k]], k );
    //         max_self( last[a[k]], k );
    //     }
    //     ll ans = 0;
    //     for(int x=1;x<=n;x++)
    //         if( last[x] != -1 )
    //         {
    //             // cout<<x<<" XX "<<last[x]<<" "<<first[x],nl;
    //             ans += last[x] - first[x];
    //         }
    //     return ans;
    // };

    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=i;j<=n;j++)
    //     {
    //         cout<<i<<" "<<j,nl;
    //         cout<<cost(i,j)<<" "<<brute(i,j),nl;
    //         nl;nl;
    //         assert( cost(i,j) == brute(i,j) );
    //     }
    // }
    // return ;

    dp[0] = 0;
    for(int x=1;x<=k;x++)
    {
        // for(int j=1;j<=n;j++)
        //     cout<<dp[j]<<" ";
        // nl;

        compute(1,n,1,n);
        dp = ndp;
    }
    cout<<dp[n];
}

int main()
{
    #ifdef gupta_samarth
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    fastio();

    int t = 1;
    // cin>>t;
    for(int test=1;test<=t;test++)
    {
        // cout<<"Case #"<<test<<": ";
        solve();
    }

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
    
### Prompt

Construct a CPP code solution to the problem outlined:

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;

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define nl cout<<"\n"
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
// const ll MOD = 998244353;
template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD ){ x += y; if( x >= m ) x -= m; }
template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD ){ x -= y; if( x < 0 ) x += m; }
ll mod( ll n, ll m=MOD ){ n%=m;if(n<0)n+=m;return n; }

const int MAXN = 35005;
const int LOGN = 21;
const ll INF = 1e17;

template<class T>
class PersistentSeg
{
public:
    int NODES, N, root;
    vector<int> L, R;
    vector<T> tree;
    T IDENTITY;
    PersistentSeg(int n)
    {
        N = n+5;
        NODES = 0;
        IDENTITY = 0;
        int lg = 0;
        for(int i=1;i<N;i<<=1,lg++);
        L.resize(8*N*lg);
        R.resize(8*N*lg);
        tree.resize(8*N*lg);
        root = build(0,N-1);
    }
    int newleaf(T val)
    {
        int p = ++NODES;
        L[p] = R[p] = 0;
        tree[p] = val;
        return p;
    }
    T merge( T x, T y )
    {
        return x+y;
    }
    int newparent(int lid, int rid)
    {
        int p = ++NODES;
        L[p] = lid;
        R[p] = rid;
        tree[p] = merge( tree[lid], tree[rid] );
        return p;
    }
    int build(int l, int r)
    {
        if( l == r )
            return newleaf(IDENTITY);
        int m = l + (r-l)/2;
        return newparent(build(l, m), build(m+1, r));
    }
    int update(int pos, T val, int node, int l, int r)
    {
        if( l == r )
            return newleaf(val);
        int m = l + (r-l)/2;
        if( pos > m )
            return newparent(L[node], update(pos, val, R[node], m+1, r));
        else
            return newparent(update(pos, val, L[node], l, m), R[node]);
    }
    T query(int ql, int qr, int node, int l, int r)
    {
        if( ql > r || qr < l )
            return IDENTITY;
        if( ql <= l && r <= qr )
            return tree[node];
        int m = l + (r-l)/2;
        return merge( query(ql, qr, L[node], l, m), query(ql, qr, R[node], m+1, r) );
    }
    int update(int pos, int val, int root)
    {
        return update(pos, val, root, 0, N-1);
    }
    T query(int ql, int qr, int root)
    {
        return query(ql, qr, root, 0, N-1);
    }
};

PersistentSeg<ll> prefix(MAXN), suffix(MAXN);
vector<int> prefix_roots(MAXN), suffix_roots(MAXN), nxt(MAXN);
vector<ll> dp(MAXN, INF), ndp(MAXN, INF);
int n, k;

ll cost(int i, int j)
{
    // cout<<i<<" "<<j,nl;
    // return 0;
    if( i > j ) return 0;
    ll psum = ( ( 1 <= j && j <= n ) ? prefix.query(i,j,prefix_roots[j]) : 0 );
    ll ssum = ( ( 1 <= i && i <= n ) ? suffix.query(i,j,suffix_roots[i]) : 0 );
    return psum + ssum;
}

void compute(int l, int r, int optl, int optr)
{
    if( l > r )
        return;

    int mid = l + (r-l)/2;

    pair<ll,ll> best = {INF, mid};
    ll temp = cost(optr+1, mid);
    for(int k=min(mid, optr); k>=max(1,optl); k--)
    {
        if( nxt[k] <= mid )
            temp += ( nxt[k] - k );
        best = min( best, { ( k-1 >= 0 ? dp[k-1] : 0 ) + temp, k } );
    }

    ndp[mid] = best.first;
    int opt = best.second;

    compute(l,mid-1,optl,opt);
    compute(mid+1,r,opt,optr);
}


void solve()
{
    cin>>n>>k;

    vector<ll> a(n+5);

    for(int i=1;i<=n;i++)
        cin>>a[i];

    vector<int> prv(n+5,n+1);
    for(int i=n;i>=1;i--)
    {
        nxt[i] = prv[a[i]];
        prv[a[i]] = i;
    }

    prv.assign(n+5,-1);
    int st = prefix.root;
    prefix_roots[0] = st;
    for(int i=1;i<=n;i++)
    {
        int val = a[i];

        if( prv[val] != -1 )
            st = prefix.update(prv[val], 0, st);
        prv[val] = i;

        st = prefix.update(prv[val], i, st);
        prefix_roots[i] = st;


        // for(int j=1;j<=n;j++)
        // {
        //     cout<<prefix.query(j,j,st)<<" ";
        // }
        // nl;
    }

    prv.assign(n+5,-1);
    st = suffix.root;
    suffix_roots[n+1] = st;
    for(int i=n;i>=1;i--)
    {
        int val = a[i];

        if( prv[val] != -1 )
            st = suffix.update(prv[val], 0, st);
        prv[val] = i;

        st = suffix.update(prv[val], -i, st);
        suffix_roots[i] = st;

        // for(int j=1;j<=n;j++)
        // {
        //     cout<<suffix.query(j,j,st)<<" ";
        // }
        // nl;
    }

    // for( auto x : prefix_roots )
    //     cout<<x<<" ";
    // nl;

    // for( auto x : suffix_roots )
    //     cout<<x<<" ";
    // nl;

    // return;

    // auto brute = [&](int i, int j)
    // {
    //     vector<int> first(n+1,n), last(n+1,-1);
    //     for(int k=i;k<=j;k++)
    //     {
    //         min_self( first[a[k]], k );
    //         max_self( last[a[k]], k );
    //     }
    //     ll ans = 0;
    //     for(int x=1;x<=n;x++)
    //         if( last[x] != -1 )
    //         {
    //             // cout<<x<<" XX "<<last[x]<<" "<<first[x],nl;
    //             ans += last[x] - first[x];
    //         }
    //     return ans;
    // };

    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=i;j<=n;j++)
    //     {
    //         cout<<i<<" "<<j,nl;
    //         cout<<cost(i,j)<<" "<<brute(i,j),nl;
    //         nl;nl;
    //         assert( cost(i,j) == brute(i,j) );
    //     }
    // }
    // return ;

    dp[0] = 0;
    for(int x=1;x<=k;x++)
    {
        // for(int j=1;j<=n;j++)
        //     cout<<dp[j]<<" ";
        // nl;

        compute(1,n,1,n);
        dp = ndp;
    }
    cout<<dp[n];
}

int main()
{
    #ifdef gupta_samarth
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    fastio();

    int t = 1;
    // cin>>t;
    for(int test=1;test<=t;test++)
    {
        // cout<<"Case #"<<test<<": ";
        solve();
    }

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
    
```