P868F

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll nmax = 1e9+7;
const ll nmax2 = 998244353;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<std::pair<ll, ll>, null_type, less<std::pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_pair;

ll l_ = 0;
ll r_ = 0;
ll cost = 0;
ll dp[21][100001];

std::vector<ll> cnt(100001);
std::vector<ll> a(100001);

void prepare(ll n, ll k) {
    for (ll i = 0; i <= k; i++){
        for (ll j = 0; j <= n; j++) dp[i][j] = LLONG_MAX;
    }

    for (ll i = 1; i <= k; i++) dp[i][0] = 0;
    for (ll i = 0; i <= n; i++) dp[0][i] = 0;

    for (ll i = 1; i <= k; i++) {
        for (ll j = 0; j < i; j++) dp[i][j] = 0;
    }

    for (ll i = 1; i <= n; i++){
        cnt[a[i]]++;
        cost += (cnt[a[i]] - 1);
        dp[1][i] = cost;
    }
}

void divide_and_conquer(ll j, ll l, ll r, ll L, ll R) {
    ll mid = (l + r) >> 1;
    if (l > r) return;

    while (r_ < mid) {
        cnt[a[++r_]]++;
        cost += (cnt[a[r_ - 1]] - 1);
    }
    while (r_ > mid) {
        cnt[a[r_--]]--;
        cost -= (cnt[a[r_ + 1]]);
    }
    while (l_ < L) {
        cnt[a[l_++]]--;
        cost -= (cnt[a[l_ - 1]]);
    }
    while (l_ > L) {
        cnt[a[--l_]]++;
        cost += (cnt[a[l_ + 1]] - 1);
    }

    ll optimal = LLONG_MAX;
    ll M = L;

    for (ll i = L; i <= R; i++) {
        if (i > mid) break;

        while (l_ < i) {
            cnt[a[l_++]]--;
            cost -= (cnt[a[l_]]);
        }

        dp[j][mid] = std::min(dp[j][mid], dp[j - 1][i - 1] + cost);

        if (optimal > dp[j][mid]) {
            optimal = dp[j][mid];
            M = i;
        }
    }

    divide_and_conquer(j, l, mid - 1, L, M);
    divide_and_conquer(j, mid + 1, r, R, M);
}

void solve() {
    ll n, k;
    std::cin >> n >> k;

    for (ll i = 1; i <= n; i++) std::cin >> a[i];

    prepare(n, k);

    for (ll i = 2; i <= k; i++) {
        for (ll j = 0; j <= n; j++) cnt[j] = 0;

        cost = 0;
        l_ = 0;
        r_ = 0;

        divide_and_conquer(i, i, n, i, n);
    }

    std::cout << dp[k][n] << '\n';
}

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    // std::cin >> t;
    while(t--) {
        solve();
    }
}