#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const LL kInf = 0x3f3f3f3f3f3f3f3fll;
const int kMaxN = 5010;
int n, k, h[kMaxN], tot_val, t[kMaxN];
LL cnt[kMaxN], w[kMaxN][kMaxN], dp[kMaxN][2];
int d[kMaxN][kMaxN];
void Modify(int p, LL v) {
  for (; p <= tot_val; p += p & (-p)) cnt[p] += v;
}
LL Query(int p) {
  LL ret = 0;
  for (; p > 0; p -= p & (-p)) ret += cnt[p];
  return ret;
}
int main() {
#ifdef local
  freopen("pro.in", "r", stdin);
#endif
  scanf("%d%d", &n, &k);
  //	printf("%d %d\n",n,k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &h[i]);
    t[i] = h[i];
  }
  sort(t + 1, t + 1 + n);
  int pos = 0;
  t[0] = -kInf;
  for (int i = 1; i <= n; i++) {
    if (t[i] != t[pos]) t[++pos] = t[i];
  }
  tot_val = pos;
  for (int i = 1; i <= n; i++) h[i] = lower_bound(t + 1, t + 1 + n, h[i]) - t;
  for (int i = 1; i <= n; i++) {
    Modify(h[i], 1);
    for (int j = i + 1; j <= n; j++) {
      w[i][j] = w[i][j - 1] + j - i - Query(h[j]);
      Modify(h[j], 1);
    }
    memset(cnt, 0, sizeof(cnt));
  }
  memset(dp, 0x3f, sizeof(dp));
  dp[0][0] = 0;
  for (int j = 1; j <= k; j++) {
    d[n + 1][j] = n;
    for (int i = n; i >= j; i--) {
      for (int t = d[i][j - 1]; t <= d[i + 1][j]; t++) {
        if (dp[t][(j - 1) & 1] + w[t + 1][i] < dp[i][j & 1]) {
          dp[i][j & 1] = dp[t][(j - 1) & 1] + w[t + 1][i];
          d[i][j] = t;
        }
      }
    }
  }
  printf("%lld\n", dp[n][k & 1]);
  return 0;
}