cf 1051 Div.2 D2. Inversion Graph Coloring (Hard Version)

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

typedef long long LL;
const int maxn = 2000 + 100;
const LL MOD = 1000000007;
int T, n, nn;
LL ans;
int a[maxn];
LL mxsum[maxn][maxn], secsum[maxn][maxn];

int lowbit(int x) {
    return x & (-x);
}

void add(LL *sum, int idx, LL x) {
    while (idx <= nn) {
        sum[idx] = (sum[idx] + x) % MOD;
        idx += lowbit(idx);
    }
}

void init() {
    nn = n + 1;
    for (int i = 1; i <= nn; ++i) {
        memset(mxsum[i] + 1, 0, sizeof(LL) * nn);
        memset(secsum[i] + 1, 0, sizeof(LL) * nn);
    }
    add(mxsum[1], 1, 1);
    add(secsum[1], 1, 1);
}

LL query(LL *sum, int idx) {
    LL ret = 0;
    while (idx > 0) {
        ret += sum[idx];
        idx -= lowbit(idx);
    }
    return ret % MOD;
}

int main(){
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> T;
    while (T--) {
        cin >> n;
        init();
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            ++a[i];
        }
        for (int i = 1; i <= n; ++i) {
            for (int sec = 1; sec < a[i]; ++sec) {
                LL tmp = query(secsum[sec], a[i]);
                add(mxsum[a[i]], sec, tmp);
                add(secsum[sec], a[i], tmp);
            }
            for (int mx = a[i] + 1; mx <= nn; ++mx) {
                LL tmp = query(mxsum[mx], a[i]);
                add(mxsum[mx], a[i], tmp);
                add(secsum[a[i]], mx, tmp);
            }
        }
        ans = 0;
        for (int i = 1; i <= nn; ++i) {
            ans += query(mxsum[i], nn);
        }
        cout << (ans % MOD) << endl;
    }

    return 0;
}