/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

int n, k, a[35005], lst[35005];
int segtree[140005][101], lazy[140005][101];

void push(int id, int k) {
    int t = lazy[id][k];
    segtree[id * 2][k] += t;
    segtree[id * 2 + 1][k] += t;
    lazy[id * 2][k] += t;
    lazy[id * 2 + 1][k] += t;
    lazy[id][k] = 0;
}

void update(int id, int l, int r, int pos, int k, int val) {
    if (l == r) {
        segtree[id][k] = val;
        return;
    }

    push(id, k);
    int m = (l + r)/2;
    if (pos <= m) update(id * 2, l, m, pos, k, val);
    else update(id * 2 + 1, m + 1, r, pos, k, val);

    segtree[id][k] = min(segtree[id * 2][k], segtree[id * 2 + 1][k]);
}

void add(int id, int l, int r, int tl, int tr, int k, int val) {
    if (l > tr || r < tl) return;
    if (l >= tl && r <= tr) {
        segtree[id][k] += val;
        lazy[id][k] += val;
        return;
    }

    push(id, k);
    int m = (l + r)/2;
    add(id * 2, l, m, tl, tr, k, val);
    add(id * 2 + 1, m + 1, r, tl, tr, k, val);

    segtree[id][k] = min(segtree[id * 2][k], segtree[id * 2 + 1][k]);
}

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> k;
    for1(i,1,n) cin >> a[i];

    for1(i,1,4 * n) {
        for1(j,0,k) segtree[i][j] = INF;
    }

    update(1, 0, n, 0, 0, 0);
    for1(i,1,n) {
        if (lst[a[i]]) for1(j,0,k) add(1, 0, n, 0, lst[a[i]] - 1, j, i - lst[a[i]]);
        lst[a[i]] = i;
        for2(j,k,1) {
            update(1, 0, n, i, j, segtree[1][j - 1]);
            if (i == n && j == k) cout << segtree[1][j - 1];
        }
    }
    
}
### Prompt

Your task is to create a Cpp solution 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
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

int n, k, a[35005], lst[35005];
int segtree[140005][101], lazy[140005][101];

void push(int id, int k) {
    int t = lazy[id][k];
    segtree[id * 2][k] += t;
    segtree[id * 2 + 1][k] += t;
    lazy[id * 2][k] += t;
    lazy[id * 2 + 1][k] += t;
    lazy[id][k] = 0;
}

void update(int id, int l, int r, int pos, int k, int val) {
    if (l == r) {
        segtree[id][k] = val;
        return;
    }

    push(id, k);
    int m = (l + r)/2;
    if (pos <= m) update(id * 2, l, m, pos, k, val);
    else update(id * 2 + 1, m + 1, r, pos, k, val);

    segtree[id][k] = min(segtree[id * 2][k], segtree[id * 2 + 1][k]);
}

void add(int id, int l, int r, int tl, int tr, int k, int val) {
    if (l > tr || r < tl) return;
    if (l >= tl && r <= tr) {
        segtree[id][k] += val;
        lazy[id][k] += val;
        return;
    }

    push(id, k);
    int m = (l + r)/2;
    add(id * 2, l, m, tl, tr, k, val);
    add(id * 2 + 1, m + 1, r, tl, tr, k, val);

    segtree[id][k] = min(segtree[id * 2][k], segtree[id * 2 + 1][k]);
}

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> k;
    for1(i,1,n) cin >> a[i];

    for1(i,1,4 * n) {
        for1(j,0,k) segtree[i][j] = INF;
    }

    update(1, 0, n, 0, 0, 0);
    for1(i,1,n) {
        if (lst[a[i]]) for1(j,0,k) add(1, 0, n, 0, lst[a[i]] - 1, j, i - lst[a[i]]);
        lst[a[i]] = i;
        for2(j,k,1) {
            update(1, 0, n, i, j, segtree[1][j - 1]);
            if (i == n && j == k) cout << segtree[1][j - 1];
        }
    }
    
}
```