1_3

#include <bits/stdc++.h>

using namespace std;

int dp[2005][2005];
int sum[2005][2005];
int tree[8005];

void update(int v, int tl, int tr, int pos)
{
    if (tl == tr)
    {
        tree[v] = 1;
        return;
    }
    int tm = (tl + tr) >> 1;
    if (pos <= tm)
        update(v * 2, tl, tm, pos);
    else
        update(v * 2 + 1, tm + 1, tr, pos);
    tree[v] = tree[v * 2] + tree[v * 2 + 1];
}

int findSum(int v, int tl, int tr, int l, int r)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return tree[v];
    int tm = (tl + tr) >> 1;
    return findSum(v * 2, tl, tm, l, min(r, tm)) +
           findSum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
}

vector<int> v, pos;

bool IsLess(int a, int b)
{
    return v[a] < v[b];
}

int main()
{
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    v.resize(n);
    pos.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        pos[i] = i;
    }
    sort(pos.begin(), pos.end(), IsLess);
    for (int i = 0; i < n; i++)
        v[ pos[i] ] = i;

    for (int i = 0; i < n; i++)
    {
        fill(tree, tree + 8005, 0);
        update(1, 0, n - 1, v[i]);
        for (int j = i + 1; j < n; j++)
        {
            sum[i][j] = sum[i][j - 1] + findSum(1, 0, n - 1, v[j], n - 1);
            update(1, 0, n - 1, v[j]);
        }
    }
    fill(dp[0], dp[0] + 100000, -1e9 + 7);
    for (int i = 0; i < n; i++)
        dp[0][i] = sum[0][i];

    for (int i = 1; i < k; i++)
        for (int j = i; j < n; j++)
        {
            dp[i][j] = 1e9 + 7;
            for (int z = 1; z <= j - i + 1; z++)
                dp[i][j] = min(dp[i][j], dp[i - 1][j - z] + sum[j - z + 1][j]);
        }
    cout << dp[k - 1][n - 1];
    return 0;
}