/// HuDzG - NHDanDz "Elderwood" (DangCuto Dep Trai vcl)
#include <bits/stdc++.h>
#define reset(a) memset(a,0,sizeof(a))
#define ll int
#define ld long double
#define endl '\n'
#define AutoAC int main()
#define OO 1000000007
#define F first
#define S second
#define pii pair <ll, ll>
#define pb push_back
#define nmax 35005
#define HUNGIT "C"
#define MOD 1000000007

using namespace std;

const ll M = 10000000;

ll n, k, a[nmax], pre[nmax], cnt = 0, f[nmax][105];
// ll cost[nmax][nmax];

// void sub1()
// {
//     for (int i = 1; i <= n; i++)
//     {
//         for (int j = 1; j <= n; j++)
//             pre[j] = 0;
//         for (int j = i; j <= n; j++)
//         {
//             cost[i][j] = cost[i][j - 1];
//             if (pre[a[j]]) cost[i][j] += j - pre[a[j]];
//             pre[a[j]] = j;
//         }
//     }
//     for (int i = 1; i <= n; i++)
//     {
//         f[i][1] = cost[1][i];
//         for (int h = 2; h <= k; h++)
//         {
//             f[i][h] = OO;
//             if (h <= i)
//             {
//                 for (int j = 1; j < i; j++)
//                     f[i][h] = min(f[i][h], f[j][h - 1] + cost[j + 1][i]);
//             }
//         }
//     }
//     for (int j = 1; j <= n; j++)
//             pre[j] = 0;
//     cout << f[n][k] << endl;
// }

pii ST[4 * nmax];

void down(ll id)
{
    ll tmp = ST[id].S;
    ST[(id << 1)].F += tmp;
    ST[(id << 1)].S += tmp;
    ST[(id << 1) + 1].F += tmp;
    ST[(id << 1) + 1].S += tmp;
    ST[id].S = 0;
}

void Build(ll t, ll id, ll l, ll r)
{
    ST[id].S = 0;
    if (l == r)
    {
        ST[id].F = f[l][t];
        return;
    }
    ll mid = ((l + r) >> 1);
    Build(t, (id << 1), l, mid);
    Build(t, (id << 1) + 1, mid + 1, r);
    ST[id].F = min(ST[(id << 1)].F, ST[(id << 1) + 1].F);
}

void Update(ll id, ll l, ll r, ll x, ll y, ll val)
{
    if (r < x || y < l) return;
    if (x <= l && r <= y)
    {
        ST[id].F += val;
        ST[id].S += val;
        return;
    }
    down(id);
    ll mid = ((l + r) >> 1);
    Update((id << 1), l, mid, x, y, val);
    Update((id << 1) + 1, mid + 1, r, x, y, val);
    ST[id].F = min(ST[(id << 1)].F, ST[(id << 1) + 1].F);
}

ll Get(ll id, ll l, ll r, ll x, ll y)
{
    if (r < x || y < l) return OO;
    if (x <= l && r <= y) return ST[id].F;
    down(id);
    ll mid = ((l + r) >> 1);
    return min(Get((id << 1), l, mid, x, y), Get((id << 1) + 1, mid + 1, r, x, y));
}

void sub2()
{
    for (int i = 1; i <= n; i++)
    {
        ll h = 1;
        f[i][1] = f[i - 1][1];
        if (pre[a[i]]) f[i][1] += i - pre[a[i]];
        // cout << h << " " << i << " " << f[i][h] << endl;
        pre[a[i]] = i;
    }
    Build(1, 1, 1, n);
    for (int h = 2; h <= k; h++)
    {
        for (int i = 1; i <= n; i++)
            pre[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            if (pre[a[i]] > 1) Update(1, 1, n, 1, pre[a[i]] - 1, i - pre[a[i]]);
            if (h > i) f[i][h] = OO;
            else f[i][h] = Get(1, 1, n, 1, i - 1);
            // cout << h << " " << i << " " << f[i][h] << endl;
            pre[a[i]] = i;
        }
        Build(h, 1, 1, n);
    }
    cout << f[n][k];
}

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // sub1();
    sub2();
}

AutoAC
{
    // clock_t START, FINISH;
    // START = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen (HUNGIT".inp", "r", stdin);
    // freopen (HUNGIT".out", "w", stdout);
    ll T = 1;

    // cin >> T;

    for (int i = 1; i <= T; i++)
    {
        solve();
    }

    // FINISH = clock();
    // cout << fixed << setprecision(4);
    // cout << endl << "TIME: " << (ld)((ld)(FINISH - START) / CLOCKS_PER_SEC);
    return 0;
}


### Prompt

Develop a solution in cpp 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
/// HuDzG - NHDanDz "Elderwood" (DangCuto Dep Trai vcl)
#include <bits/stdc++.h>
#define reset(a) memset(a,0,sizeof(a))
#define ll int
#define ld long double
#define endl '\n'
#define AutoAC int main()
#define OO 1000000007
#define F first
#define S second
#define pii pair <ll, ll>
#define pb push_back
#define nmax 35005
#define HUNGIT "C"
#define MOD 1000000007

using namespace std;

const ll M = 10000000;

ll n, k, a[nmax], pre[nmax], cnt = 0, f[nmax][105];
// ll cost[nmax][nmax];

// void sub1()
// {
//     for (int i = 1; i <= n; i++)
//     {
//         for (int j = 1; j <= n; j++)
//             pre[j] = 0;
//         for (int j = i; j <= n; j++)
//         {
//             cost[i][j] = cost[i][j - 1];
//             if (pre[a[j]]) cost[i][j] += j - pre[a[j]];
//             pre[a[j]] = j;
//         }
//     }
//     for (int i = 1; i <= n; i++)
//     {
//         f[i][1] = cost[1][i];
//         for (int h = 2; h <= k; h++)
//         {
//             f[i][h] = OO;
//             if (h <= i)
//             {
//                 for (int j = 1; j < i; j++)
//                     f[i][h] = min(f[i][h], f[j][h - 1] + cost[j + 1][i]);
//             }
//         }
//     }
//     for (int j = 1; j <= n; j++)
//             pre[j] = 0;
//     cout << f[n][k] << endl;
// }

pii ST[4 * nmax];

void down(ll id)
{
    ll tmp = ST[id].S;
    ST[(id << 1)].F += tmp;
    ST[(id << 1)].S += tmp;
    ST[(id << 1) + 1].F += tmp;
    ST[(id << 1) + 1].S += tmp;
    ST[id].S = 0;
}

void Build(ll t, ll id, ll l, ll r)
{
    ST[id].S = 0;
    if (l == r)
    {
        ST[id].F = f[l][t];
        return;
    }
    ll mid = ((l + r) >> 1);
    Build(t, (id << 1), l, mid);
    Build(t, (id << 1) + 1, mid + 1, r);
    ST[id].F = min(ST[(id << 1)].F, ST[(id << 1) + 1].F);
}

void Update(ll id, ll l, ll r, ll x, ll y, ll val)
{
    if (r < x || y < l) return;
    if (x <= l && r <= y)
    {
        ST[id].F += val;
        ST[id].S += val;
        return;
    }
    down(id);
    ll mid = ((l + r) >> 1);
    Update((id << 1), l, mid, x, y, val);
    Update((id << 1) + 1, mid + 1, r, x, y, val);
    ST[id].F = min(ST[(id << 1)].F, ST[(id << 1) + 1].F);
}

ll Get(ll id, ll l, ll r, ll x, ll y)
{
    if (r < x || y < l) return OO;
    if (x <= l && r <= y) return ST[id].F;
    down(id);
    ll mid = ((l + r) >> 1);
    return min(Get((id << 1), l, mid, x, y), Get((id << 1) + 1, mid + 1, r, x, y));
}

void sub2()
{
    for (int i = 1; i <= n; i++)
    {
        ll h = 1;
        f[i][1] = f[i - 1][1];
        if (pre[a[i]]) f[i][1] += i - pre[a[i]];
        // cout << h << " " << i << " " << f[i][h] << endl;
        pre[a[i]] = i;
    }
    Build(1, 1, 1, n);
    for (int h = 2; h <= k; h++)
    {
        for (int i = 1; i <= n; i++)
            pre[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            if (pre[a[i]] > 1) Update(1, 1, n, 1, pre[a[i]] - 1, i - pre[a[i]]);
            if (h > i) f[i][h] = OO;
            else f[i][h] = Get(1, 1, n, 1, i - 1);
            // cout << h << " " << i << " " << f[i][h] << endl;
            pre[a[i]] = i;
        }
        Build(h, 1, 1, n);
    }
    cout << f[n][k];
}

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // sub1();
    sub2();
}

AutoAC
{
    // clock_t START, FINISH;
    // START = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen (HUNGIT".inp", "r", stdin);
    // freopen (HUNGIT".out", "w", stdout);
    ll T = 1;

    // cin >> T;

    for (int i = 1; i <= T; i++)
    {
        solve();
    }

    // FINISH = clock();
    // cout << fixed << setprecision(4);
    // cout << endl << "TIME: " << (ld)((ld)(FINISH - START) / CLOCKS_PER_SEC);
    return 0;
}


```