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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

const int N = 35007, K = 107, INF = 1e9 + 7;

int n, k;

class Aint {
    struct Nod {
        long long ans, lazy;
    };
    Nod t[4 * N];

    int st, dr, val;

    void propaga(int nod, int l, int r) {
        if (l == r)
            return;
        t[nod<<1].ans += t[nod].lazy;
        t[nod<<1].lazy += t[nod].lazy;
        t[(nod<<1) + 1].ans += t[nod].lazy;
        t[(nod<<1) + 1].lazy += t[nod].lazy;
        t[nod].lazy = 0;
    }

    void update(int nod = 1, int l = 0, int r = n) {
        if (st <= l && r <= dr) {
            t[nod].ans += val;
            t[nod].lazy += val;
            return;
        }
        propaga(nod, l, r);
        int mij((l + r) >> 1);
        if (st <= mij)
            update(nod<<1, l, mij);
        if (dr > mij)
            update((nod<<1) + 1, mij + 1, r);
        t[nod].ans = min(t[nod<<1].ans, t[(nod<<1) + 1].ans);
    }

    int query(int nod = 1, int l = 0, int r = n) {
        if (st <= l && r <= dr)
            return t[nod].ans;
        propaga(nod, l, r);
        int mij((l + r) >> 1), ans(INF);
        if (st <= mij)
            ans = min(ans, query(nod<<1, l, mij));
        if (dr > mij)
            ans = min(ans, query((nod<<1) + 1, mij + 1, r));
        return ans;
    }

public:

    void Update(int _st, int _dr, int _val) {
        if (_st > _dr)
            return;
        st = _st;
        dr = _dr;
        val = _val;
        update();
    }

    int Query(int _st, int _dr) {
        if (_st > _dr)
            return 0;
        st = _st;
        dr = _dr;
        return query();
    }

}aint[K];

int last[N], a[N];

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    aint[0].Update(1, n, INF);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (last[a[i]]) {
            for (int j = 0; j < k; ++j)
                aint[j].Update(0, last[a[i]] - 1, i - last[a[i]]);
        }
        last[a[i]] = i;
        for (int j = 1; j <= k; ++j) {
//            int val = aint[j - 1].Query(0, i);
//            cout << val << " \n"[j == k];
            aint[j].Update(i, i, aint[j - 1].Query(0, i));
        }
    }
    cout << aint[k].Query(n, n);
    return 0;
}