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

const int N = 5e5 + 10;
int a[N], pos[N], b[N];

void solve()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }

    memcpy(b, a, sizeof(int) * (n + 1));

    int cnt = 0;

    auto dfs = [&](auto self, int l, int r) {
        if(l >= r)  return;
        if(r == l + 1) {
            if(a[l] > a[r]) swap(a[l], a[r]), swap(pos[a[l]], pos[a[r]]), cnt++;
            return;
        }
        int mid = (l + r + 1) / 2, midVal = a[mid];     
        // for(int i = 1; i <= n; i++) printf("%d ", a[i]);
        // printf("\n");
        // printf(":%d %d %d %d\n", l, r, mid, midVal);

        // getchar();
        vector<int> lp, rp;
        if(midVal < mid) {
            for(int i = l; i <= midVal; i++)    if(a[i] >= midVal)    lp.push_back(i);
            for(int v = l; v <= midVal; v++)    if(pos[v] >= midVal)     rp.push_back(pos[v]);
            sort(lp.begin(), lp.end());
            sort(rp.begin(), rp.end(), greater<int>());
        } else if(midVal >= mid) {
            for(int v = midVal; v <= r; v++)    if(pos[v] <= midVal) lp.push_back(pos[v]);
            for(int i = midVal; i <= r; i++)    if(a[i] <= midVal)   rp.push_back(i);
            sort(lp.begin(), lp.end());
            sort(rp.begin(), rp.end(), greater<int>());
        }

        for(int i = 0; i < lp.size(); i++) {
            int p1 = lp[i], p2 = rp[i];
            if(p1 == p2)    continue;
            // printf("::%d %d\n", p1, p2);
            swap(a[p1], a[p2]);
            swap(pos[a[p1]], pos[a[p2]]);
            cnt++;
        }

        self(self, l, midVal);
        self(self, midVal, r);
    };    


    int cnt2 = 0;
    auto partition = [&](int l, int r) {
        int pivot = b[(l + r + 1) / 2];
        while(1) {
            while(b[l] < pivot)     l++;
            while(b[r] > pivot)     r--;
            if(l >= r)  return r;
            swap(b[l++], b[r--]);
            cnt2++;
        }
    };
    auto sort = [&](auto self, int l, int r) -> void {
        if(l >= 0 && r >= 0 && l < r)   {
            int p = partition(l, r);
            if(p < r) self(self, l, p);
            self(self, p + 1, r);
        }
    };
    // sort(sort, 1, n);
    dfs(dfs, 1, n);
    // printf("%d %d\n", cnt, cnt2);
    printf("%d\n", cnt);
}

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--)  solve();

    return 0;
}