#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const long long inf = 1e18;
int a[N], n, k;
int cl, cr, c[N];
long long now;
void add(int p) { now += c[a[p]], ++c[a[p]]; }
void del(int p) { now -= c[a[p]] - 1, --c[a[p]]; }
long long weight(int l, int r) {
  while (cl < l) del(cl++);
  while (cr < r) add(++cr);
  while (cl > l) add(--cl);
  while (cr > r) del(cr--);
  return now;
}
void solve(long long *f, long long *g, int l, int r, int pl, int pr) {
  if (l > r || pl > pr) return;
  if (pl == pr) {
    for (int i = l; i <= r; i++) {
      f[i] = g[pl - 1] + weight(pl, i);
    }
    return;
  }
  int mid = (l + r) >> 1, pmid = -1;
  long long ans = inf * 2;
  for (int i = pl; i <= min(pr, mid); i++)
    if (g[i - 1] + weight(i, mid) < ans) {
      ans = g[i - 1] + weight(i, mid);
      pmid = i;
    }
  f[mid] = ans;
  solve(f, g, l, mid - 1, pl, pmid);
  solve(f, g, mid + 1, r, pmid, pr);
}
long long dp[23][N];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  memset(dp, 0x3f, sizeof(dp));
  dp[0][0] = 0;
  cl = 1, cr = 0, now = 0;
  for (int i = 1; i <= k; i++) solve(dp[i], dp[i - 1], 1, n, 1, n);
  printf("%lld\n", dp[k][n]);
  return 0;
}
