#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <numeric>
using namespace std;

#ifdef DBG
    #define dbg 1
    #define dpf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
    #define dbg 0
    #define dpf(...) 42
#endif
 
#define SIZE(x) int((x).size())
#define REP(i,c) for(auto &i : c)
#define pb push_back
#define eb emplace_back
typedef long long i64;
typedef unsigned long long u64;
const double EPS = 1e-12;
const int INF = 999999999;
typedef vector<int> VI;
typedef vector<string> VS;

struct SegTree {
    typedef int T;

    int max;
    vector<T> minv;
    vector<T> add;

    SegTree(int max=0) {
        Reset(max);
    }

    void Reset(int max) {
        this->max=max;
        int v=max;
        int c=1;
        while(v) {
            ++c;
            v>>=1;
        }
        minv.assign((1<<c)-1, INF);
        add.assign(SIZE(minv), 0);
    }

    void Set(int i, T v) {
        Set(i,v,0,max,0);
    }

    void AddToRange(int ql,int qr, T v) {
        qr=min(qr,max);
        if(ql>qr) return;
        AddToRange(ql,qr,v,0,max,0);
    }

    int FindMin(int l,int r) {
        if(l>r) return INF;
        return FindMin(l,r,0,max,0);
    }

private:
    void Set(int i, T v, int l, int r, int p) {
        if(i<l || i>r) return;
        if(l==r) {
            minv[p]=v;
            return;
        }
        int m=(l+r)>>1;
        int p1=(p<<1)^1,p2=p1+1;
        Propgate(p, p1, p2);
        Set(i,v,l,m,p1);
        Set(i,v,m+1,r,p2);
        UpdateForSubtreeChange(p,p1,p2);
    }

    void AddToRange(int ql,int qr, T v, int l, int r, int p) {
        if(ql>r || qr<l) return;
        if(ql<=l && qr>=r) {
            add[p]+=v;
            minv[p]+=v;
            return;
        }
        int m=(l+r)>>1;
        int p1=(p<<1)^1,p2=p1+1;
        Propgate(p, p1, p2);
        AddToRange(ql,qr,v,l,m,p1);
        AddToRange(ql,qr,v,m+1,r,p2);
        UpdateForSubtreeChange(p,p1,p2);
    }

    int FindMin(int ql,int qr, int l,int r,int p) {
        if(ql>r || qr<l) return INF;
        if(ql<=l && qr>=r) {
            return minv[p];
        }
        int m=(l+r)>>1;
        int p1=(p<<1)^1,p2=p1+1;
        Propgate(p, p1, p2);
        return min(FindMin(ql,qr,l,m,p1), FindMin(ql,qr,m+1,r,p2));
    }

    inline void Propgate(int p, int p1,int p2) {
        add[p1]+=add[p];
        if(minv[p1]!=INF) minv[p1]+=add[p];
        add[p2]+=add[p];
        if(minv[p2]!=INF) minv[p2]+=add[p];
        add[p]=0;
    }

    inline void UpdateForSubtreeChange(int p, int p1,int p2) {
        assert(add[p]==0);
        minv[p]=min(minv[p1],minv[p2]);
    }
};

const int MAXM=105;
const int MAXN=35005;

int n,m;
VI a;
VI pre_a;

// sg[k][i] = dp[k][i] + segment[i+1 .. now]
int cur;
SegTree sg[2];

void Solve() {
    scanf("%d%d",&n,&m);
    a.resize(n+1);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);

    {
        pre_a.resize(n+1);
        VI pos(n+1,-1);
        for(int i=1;i<=n;++i) {
            pre_a[i]=pos[a[i]];
            pos[a[i]]=i;
        }
    }

    cur=0;
    sg[cur].Reset(0);
    sg[cur].Set(0,0);

    int ans=INF;
    for(int nseg=1;nseg<=m;++nseg) {
        int pre=cur;
        cur^=1;
        sg[cur].Reset(n);
        sg[cur].Set(0,0);
        for(int now=1;now<=n;++now) {
            // Expand sg[pre] to now.
            if (pre_a[now]>=0) {
                int addv=now-pre_a[now];
                sg[pre].AddToRange(0,pre_a[now]-1,addv);
            }

            int dp=sg[pre].FindMin(0,now-1);
            if(nseg<m) {
                sg[cur].Set(now,dp);
            }

            if(now==n && nseg==m) ans=dp;
        }
    }
    printf("%d\n",ans);
}

int main() {
    int t=1;
    for (int i = 1; i <= t; ++i) {
        Solve();
    }

    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 <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <numeric>
using namespace std;

#ifdef DBG
    #define dbg 1
    #define dpf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
    #define dbg 0
    #define dpf(...) 42
#endif
 
#define SIZE(x) int((x).size())
#define REP(i,c) for(auto &i : c)
#define pb push_back
#define eb emplace_back
typedef long long i64;
typedef unsigned long long u64;
const double EPS = 1e-12;
const int INF = 999999999;
typedef vector<int> VI;
typedef vector<string> VS;

struct SegTree {
    typedef int T;

    int max;
    vector<T> minv;
    vector<T> add;

    SegTree(int max=0) {
        Reset(max);
    }

    void Reset(int max) {
        this->max=max;
        int v=max;
        int c=1;
        while(v) {
            ++c;
            v>>=1;
        }
        minv.assign((1<<c)-1, INF);
        add.assign(SIZE(minv), 0);
    }

    void Set(int i, T v) {
        Set(i,v,0,max,0);
    }

    void AddToRange(int ql,int qr, T v) {
        qr=min(qr,max);
        if(ql>qr) return;
        AddToRange(ql,qr,v,0,max,0);
    }

    int FindMin(int l,int r) {
        if(l>r) return INF;
        return FindMin(l,r,0,max,0);
    }

private:
    void Set(int i, T v, int l, int r, int p) {
        if(i<l || i>r) return;
        if(l==r) {
            minv[p]=v;
            return;
        }
        int m=(l+r)>>1;
        int p1=(p<<1)^1,p2=p1+1;
        Propgate(p, p1, p2);
        Set(i,v,l,m,p1);
        Set(i,v,m+1,r,p2);
        UpdateForSubtreeChange(p,p1,p2);
    }

    void AddToRange(int ql,int qr, T v, int l, int r, int p) {
        if(ql>r || qr<l) return;
        if(ql<=l && qr>=r) {
            add[p]+=v;
            minv[p]+=v;
            return;
        }
        int m=(l+r)>>1;
        int p1=(p<<1)^1,p2=p1+1;
        Propgate(p, p1, p2);
        AddToRange(ql,qr,v,l,m,p1);
        AddToRange(ql,qr,v,m+1,r,p2);
        UpdateForSubtreeChange(p,p1,p2);
    }

    int FindMin(int ql,int qr, int l,int r,int p) {
        if(ql>r || qr<l) return INF;
        if(ql<=l && qr>=r) {
            return minv[p];
        }
        int m=(l+r)>>1;
        int p1=(p<<1)^1,p2=p1+1;
        Propgate(p, p1, p2);
        return min(FindMin(ql,qr,l,m,p1), FindMin(ql,qr,m+1,r,p2));
    }

    inline void Propgate(int p, int p1,int p2) {
        add[p1]+=add[p];
        if(minv[p1]!=INF) minv[p1]+=add[p];
        add[p2]+=add[p];
        if(minv[p2]!=INF) minv[p2]+=add[p];
        add[p]=0;
    }

    inline void UpdateForSubtreeChange(int p, int p1,int p2) {
        assert(add[p]==0);
        minv[p]=min(minv[p1],minv[p2]);
    }
};

const int MAXM=105;
const int MAXN=35005;

int n,m;
VI a;
VI pre_a;

// sg[k][i] = dp[k][i] + segment[i+1 .. now]
int cur;
SegTree sg[2];

void Solve() {
    scanf("%d%d",&n,&m);
    a.resize(n+1);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);

    {
        pre_a.resize(n+1);
        VI pos(n+1,-1);
        for(int i=1;i<=n;++i) {
            pre_a[i]=pos[a[i]];
            pos[a[i]]=i;
        }
    }

    cur=0;
    sg[cur].Reset(0);
    sg[cur].Set(0,0);

    int ans=INF;
    for(int nseg=1;nseg<=m;++nseg) {
        int pre=cur;
        cur^=1;
        sg[cur].Reset(n);
        sg[cur].Set(0,0);
        for(int now=1;now<=n;++now) {
            // Expand sg[pre] to now.
            if (pre_a[now]>=0) {
                int addv=now-pre_a[now];
                sg[pre].AddToRange(0,pre_a[now]-1,addv);
            }

            int dp=sg[pre].FindMin(0,now-1);
            if(nseg<m) {
                sg[cur].Set(now,dp);
            }

            if(now==n && nseg==m) ans=dp;
        }
    }
    printf("%d\n",ans);
}

int main() {
    int t=1;
    for (int i = 1; i <= t; ++i) {
        Solve();
    }

    return 0;
}

```