#include <lastweapon/io>
#include <lastweapon/fenwicktree>
using namespace lastweapon;

const int N = int(6e3) + 9;

int a[N], f[2][N], w[N][N]; VI P; int p = 0, q = 1;
PII Q[N]; int cz, op;
int n, m;

int calc(int l, int r) {
    return f[q][l] + w[l+1][r];
}

int left(int a, int b) {
    int l = a, r = n+1;
    while (l < r) {
        int m = (l + r) / 2;
        if (calc(b, m) <= calc(a, m)) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return l;
}

int main() {
#ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
#endif

    Rush {

        RD(n, m); P.clear(); REP(i, n) P.PB(RD(a[i])); UNQ(P);

        REP(i, n) a[i] = LBD(P, a[i]);

        REP(i, n) {
            fenwick_tree<int> T(SZ(P));
            FOR(j, i+1, n) {
                T.add(a[j-1], 1);
                w[i][j] = w[i][j-1] + (j-i) - T.sum(a[j]+1);
            }
        }

        REP(i, n) f[p][i] = w[0][i];

        REP_1(s, m) {
            swap(p, q); // FLC(f[p], 0x3f);
            cz = 0, op = 0; Q[0] = {s-1, n+1};

            FOR(i, s, n) {
                //FOR(j, s-1, i) checkMin(f[p][i], calc(j, i));

                while (cz < op && Q[cz+1].se <= i) ++cz;
                int j = Q[cz].fi; f[p][i] = calc(j, i);
                //cout << j << " ";
                j = left(Q[op].fi, i);
                while (cz < op && j <= Q[op].se) j = left(Q[--op].fi, i);

                //cout << i << " "  << j << endl;

                Q[++op] = {i, j};

            }
            /*cout << endl;
            REP(i, op+1) cout << Q[i].fi << "," << Q[i].se<< " ";
            cout << endl;*/
        }

        cout << f[p][n-1] << endl;
    }

}

answer.code:1:10: fatal error: lastweapon/io: No such file or directory
    1 | #include <lastweapon/io>
      |          ^~~~~~~~~~~~~~~
compilation terminated.