// Coded by hjxddl
#include <bits/stdc++.h>
#define ll  long long
#define db  double
#define mid (l + r >> 1)
const int N = 2e5 + 5;
int n;
ll ans;
std::vector<int> a, min, max;
void build(int x = 1, int l = 1, int r = n) {
    if (l == r) {
        min[x] = max[x] = a[l];
        return;
    }
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    min[x] = std::min(min[x << 1], min[x << 1 | 1]);
    max[x] = std::max(max[x << 1], max[x << 1 | 1]);
}
int query(int opt, int k, int l1, int r1, int x = 1, int l = 1, int r = n) {
    if (l == r)
        return l;
    if (opt == 0) {
        int ans = n + 5;
        if (max[x << 1] >= k) {
            if (l1 <= mid)
                ans = std::min(ans, query(opt, k, l1, r1, x << 1, l, mid));
            if (ans == n + 5 && max[x << 1 | 1] >= k)
                return query(opt, k, l1, r1, x << 1 | 1, mid + 1, r);
            return ans;
        } else {
            if (max[x << 1 | 1] >= k)
                return query(opt, k, l1, r1, x << 1 | 1, mid + 1, r);
            return ans;
        }
    }
    if (opt == 1) {
        int ans = 0;
        if (min[x << 1 | 1] <= k) {
            if (r1 > mid)
                ans = std::max(ans, query(opt, k, l1, r1, x << 1 | 1, mid + 1, r));
            if (ans == 0 && min[x << 1] <= k)
                return query(opt, k, l1, r1, x << 1, l, mid);
            return ans;
        } else {
            if (min[x << 1] <= k)
                return query(opt, k, l1, r1, x << 1, l, mid);
            return ans;
        }
    }
}
void change(int k, int pos, int x = 1, int l = 1, int r = n) {
    if (l == r) {
        min[x] = max[x] = k;
        return;
    }
    if (pos <= mid)
        change(k, pos, x << 1, l, mid);
    else
        change(k, pos, x << 1 | 1, mid + 1, r);
    min[x] = std::min(min[x << 1], min[x << 1 | 1]);
    max[x] = std::max(max[x << 1], max[x << 1 | 1]);
}
int partition(int l, int r) {
    int p = a[mid];
    while (1) {
        int i = query(0, p, l, n);
        int j = query(1, p, 1, r);
        if (i >= j) return j;
        int x = a[i], y = a[j];
        std::swap(a[i], a[j]);
        change(x, j);
        change(y, i);
        ans++;
    }
}
void quicksort(int l, int r) {
    if (l >= 0 && r >= 0 && l < r) {
        int p = partition(l, r);
        quicksort(l, p);
        quicksort(p + 1, r);
    }
}
void solve() {
    std::cin >> n;
    ans = 0;
    a.clear();
    a.resize(n + 5);
    min.clear(), max.clear();
    min.resize((n + 5) << 2), max.resize((n + 5) << 2);
    for (int i = 1; i <= n; i++)
        std::cin >> a[i];
    build();
    quicksort(1, n);
    std::cout << ans << '\n';
}
int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    std::cout << std::flush;
}