#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define mm(a,b) memset(a,b,sizeof(a))
#define ACCELERATE (ios::sync_with_stdio(false),cin.tie(0))
#define pii pair<int,int>
#define pdd pair<double,double>
#define pll pair<long long,long long>
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define rush() int T;scanf("%d",&T);while(T--)
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define pf(a) printf("%d\n",a)
#define p_f(a) printf("%d ",a)
#define pf2(a,b) printf("%d %d\n",a,b)
#define pf3(a,b,c) printf("%d %d %d\n",a,b,c)
#define debug(x) cout<<#x<<": "<<x<<endl
#define all(x) (x).begin(),(x).end()
#define PI acos(-1.0)
#define E exp(1.0)
#define ll long long
//#define int long long
#define ld long double
#define ull unsigned long long
//#define io
using namespace std;
//#define gc getchar
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read(){
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;else return ret;
}
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 35000 + 5;
const int K = 1e2 + 5;
int n, k, x, a[N], lasti[N], dp[N][K], t[N];
struct node{
    int l, r, x, a;
}tr[N << 2];
void build(int k, int l, int r)
{
    tr[k].l = l; tr[k].r = r; tr[k].a = 0;
    if (l == r) {
        tr[k].x = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    tr[k].x = min(tr[k << 1].x, tr[k << 1 | 1].x);
}
void push_down(int k)
{
    tr[k << 1].a += tr[k].a;
    tr[k << 1 | 1].a += tr[k].a;
    tr[k << 1].x += tr[k].a;
    tr[k << 1 | 1].x += tr[k].a;
    tr[k].a = 0;
}
void update(int k, int x, int y, int v)
{
    int l = tr[k].l, r = tr[k].r;
    if (l == x && r == y) {
        tr[k].x += v;
        tr[k].a += v;
        return ;
    }
    if (tr[k].a && l != r) push_down(k);
    int mid = (l + r) >> 1;
    if (y <= mid) update(k << 1, x, y, v);
    else if (x > mid) update(k << 1 | 1, x, y, v);
    else update(k << 1, x, mid, v), update(k << 1 | 1, mid + 1, y, v);
    tr[k].x = min(tr[k << 1].x, tr[k << 1 | 1].x);
}
int query(int k, int x, int y)
{
    int l = tr[k].l, r = tr[k].r;
    if (l >= x && r <= y) {
        return tr[k].x;
    }
    if (tr[k].a && l != r) push_down(k);
    int mid = (l + r) >> 1;
    if (y <= mid) return query(k << 1, x, y);
    else if (x > mid) return query(k << 1 | 1, x, y);
    else return min(query(k << 1, x, mid), query(k << 1 | 1, mid + 1, y));
}
signed main()
{
    sc2(n, k);
    rep(i, 1, n) {
        sc(x);
        t[i] = x;
        lasti[i] = (a[x] == 0 ? 0 : a[x]);
        a[x] = i;
    }
    dp[1][1] = 0;
    rep(i, 2, n) dp[i][1] = dp[i - 1][1] + (lasti[i] == 0 ? 0 :i - lasti[i]);
    rep(j, 2, k) {
        rep(i, 1, n) a[i] = dp[i][j - 1];
        build(1, 1, n);
        rep(i, 1, j - 1) dp[i][j] = inf;
        dp[j][j] = 0;
        rep(i, j + 1, n) {
            int last = lasti[i];
            if (last != 0 && last > j - 1) {
                update(1, j - 1, last - 1, i - last);
            }
            dp[i][j] = query(1, j - 1, i - 1);
        }
    }
    pf(dp[n][k]);
    return 0;
}

### Prompt

Please provide a cpp coded solution 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>
#pragma GCC optimize(2)
#define mm(a,b) memset(a,b,sizeof(a))
#define ACCELERATE (ios::sync_with_stdio(false),cin.tie(0))
#define pii pair<int,int>
#define pdd pair<double,double>
#define pll pair<long long,long long>
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define rush() int T;scanf("%d",&T);while(T--)
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define pf(a) printf("%d\n",a)
#define p_f(a) printf("%d ",a)
#define pf2(a,b) printf("%d %d\n",a,b)
#define pf3(a,b,c) printf("%d %d %d\n",a,b,c)
#define debug(x) cout<<#x<<": "<<x<<endl
#define all(x) (x).begin(),(x).end()
#define PI acos(-1.0)
#define E exp(1.0)
#define ll long long
//#define int long long
#define ld long double
#define ull unsigned long long
//#define io
using namespace std;
//#define gc getchar
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read(){
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;else return ret;
}
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 35000 + 5;
const int K = 1e2 + 5;
int n, k, x, a[N], lasti[N], dp[N][K], t[N];
struct node{
    int l, r, x, a;
}tr[N << 2];
void build(int k, int l, int r)
{
    tr[k].l = l; tr[k].r = r; tr[k].a = 0;
    if (l == r) {
        tr[k].x = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    tr[k].x = min(tr[k << 1].x, tr[k << 1 | 1].x);
}
void push_down(int k)
{
    tr[k << 1].a += tr[k].a;
    tr[k << 1 | 1].a += tr[k].a;
    tr[k << 1].x += tr[k].a;
    tr[k << 1 | 1].x += tr[k].a;
    tr[k].a = 0;
}
void update(int k, int x, int y, int v)
{
    int l = tr[k].l, r = tr[k].r;
    if (l == x && r == y) {
        tr[k].x += v;
        tr[k].a += v;
        return ;
    }
    if (tr[k].a && l != r) push_down(k);
    int mid = (l + r) >> 1;
    if (y <= mid) update(k << 1, x, y, v);
    else if (x > mid) update(k << 1 | 1, x, y, v);
    else update(k << 1, x, mid, v), update(k << 1 | 1, mid + 1, y, v);
    tr[k].x = min(tr[k << 1].x, tr[k << 1 | 1].x);
}
int query(int k, int x, int y)
{
    int l = tr[k].l, r = tr[k].r;
    if (l >= x && r <= y) {
        return tr[k].x;
    }
    if (tr[k].a && l != r) push_down(k);
    int mid = (l + r) >> 1;
    if (y <= mid) return query(k << 1, x, y);
    else if (x > mid) return query(k << 1 | 1, x, y);
    else return min(query(k << 1, x, mid), query(k << 1 | 1, mid + 1, y));
}
signed main()
{
    sc2(n, k);
    rep(i, 1, n) {
        sc(x);
        t[i] = x;
        lasti[i] = (a[x] == 0 ? 0 : a[x]);
        a[x] = i;
    }
    dp[1][1] = 0;
    rep(i, 2, n) dp[i][1] = dp[i - 1][1] + (lasti[i] == 0 ? 0 :i - lasti[i]);
    rep(j, 2, k) {
        rep(i, 1, n) a[i] = dp[i][j - 1];
        build(1, 1, n);
        rep(i, 1, j - 1) dp[i][j] = inf;
        dp[j][j] = 0;
        rep(i, j + 1, n) {
            int last = lasti[i];
            if (last != 0 && last > j - 1) {
                update(1, j - 1, last - 1, i - last);
            }
            dp[i][j] = query(1, j - 1, i - 1);
        }
    }
    pf(dp[n][k]);
    return 0;
}

```