#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
int t[N];
int lowbit(int x) { return x & -x; }
void add(int x, int y) {
    while (x) t[x] += y, x -= lowbit(x);
}
int query(int x, int n) {
    int ans = 0;
    while (x <= n) ans += t[x], x += lowbit(x);
    return ans;
}
int p[N], q[N], f[N];
void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i], q[p[i]] = i, t[i] = 0;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += query(p[i], n);
        add(p[i], 1);
    }
    for (int i = 2; i <= n; i++) {
        f[i] = f[i - 1];
        f[i] = max(f[i], f[i - 2] + (q[i - 1] > q[i]));
    }
    cout << ans - f[n] << '\n';
}
int main() {
    int T; cin >> T;
    while (T--) solve();
}