#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (n); i += 1)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(a) ((int)(a).size())

mt19937 rnd(234);
const ll inf = 1e18;

const int maxn = 1e3 + 100;
int n;
int h[maxn];
int dp[maxn];
int cntl[maxn], cntr[maxn];
int s[2 * maxn];

int solve() {
    dp[0] = 0;
    for (int i = 1; i <= n; i += 1) {
        dp[i] = 10 * n + 100;
    }
    for (int i = 1; i + 1 < n; i += 1) {
        cntl[i] = cntr[i] = 0;
        for (int l = i - 1, r = i + 1; l >= 0 and r <= n - 1; l -= 1, r += 1) {
            cntl[l] = cntr[l] = cntl[r] = cntr[r] = 0;
            if (h[l] < h[r]) {
                cntr[l] += 1;
            } else {
                cntl[r] += 1;
            }
            for (int j = l + 1; j <= r - 1; j += 1) {
                cntr[l] += (h[j] > h[l]);
                cntl[j] += (h[l] > h[j]);
                cntl[r] += (h[j] > h[r]);
                cntr[j] += (h[r] > h[j]);
            }
            int opt = 0;
            for (int j = l; j <= r; j += 1) {
                opt += cntl[j];
            }
            int k = i - l;
            for (int j = 0; j <= 4 * k; ++j) {
                s[j] = 0;
            }
            for (int j = l; j <= r; j += 1) {
                if (cntr[j] != 0 or cntl[j] != 0) {
                    s[cntr[j] - cntl[j] + 2 * k] += 1;
                }
            }
            int num = k;
            for (int j = 0; j <= 4 * k && num > 0; j += 1) {
                while (num > 0 and s[j] > 0) {
                    --num;
                    --s[j];
                    opt += j - 2 * k;
                }
            }
            dp[r + 1] = min(dp[r + 1], dp[l] + opt);
        }
    }
    return dp[n];
}

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int t;
    cin >> t;
    rep(itr, t) {
        cin >> n;
        rep(i, n) {
            cin >> h[i];
        }
        int res = solve();
        cout << res << "\n";
    }
    return 0;
}

/*
1
6
1 2 4 8 16 32


4
3
1 3 2
6
1 2 4 8 16 32
5
1 2 3 4 5
7
6 4 2 1 3 5 7
*/