#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int N = 5E5 + 5;

int n, a[N];

struct Data {
    int min = 1E9, max = -1E9;
} ;
Data operator+(const Data &lhs, const Data &rhs) {
    return (Data) {
        std::min(lhs.min, rhs.min),
        std::max(lhs.max, rhs.max)
    } ;
}

struct SegmentTree {
    Data t[N * 4];

    void pull(int x) {
        t[x] = t[x * 2] + t[x * 2 + 1];
    }
    void build(int x, int l, int r) {
        if (l == r) return void(t[x] = {a[l], a[l]});
        int mid = (l + r) / 2;
        build(x * 2, l, mid);
        build(x * 2 + 1, mid + 1, r);
        pull(x);
    }
    void modify(int x, int l, int r, int pos, int val) {
        if (l == r) return void(t[x] = {val, val});
        int mid = (l + r) / 2;
        if (pos <= mid) modify(x * 2, l, mid, pos, val);
        else modify(x * 2 + 1, mid + 1, r, pos, val);
        pull(x);
    }
    void modify(int pos, int val) {modify(1, 1, n, pos, val);}
    int fft(int x, int l, int r, int lim) {
        if (l == r) return l;
        int mid = (l + r) / 2;
        if (t[x * 2].max >= lim) return fft(x * 2, l, mid, lim);
        return fft(x * 2 + 1, mid + 1, r, lim);
    }
    int flt(int x, int l, int r, int lim) {
        if (l == r) return l;
        int mid = (l + r) / 2;
        if (t[x * 2 + 1].min <= lim) return flt(x * 2 + 1, mid + 1, r, lim);
        return flt(x * 2, l, mid, lim);
    }
    int ff(int x, int l, int r, int L, int R, int lim) {
        if (r < L || l > R) return -1;
        if (l >= L && r <= R) {
            if (t[x].max >= lim) return fft(x, l, r, lim);
            else return -1;
        }
        int mid = (l + r) / 2, res = ff(x * 2, l, mid, L, R, lim);
        if (~res) return res;
        return ff(x * 2 + 1, mid + 1, r, L, R, lim);
    }
    int ff(int l, int r, int lim) {return ff(1, 1, n, l, r, lim);}
    int fl(int x, int l, int r, int L, int R, int lim) {
        if (r < L || l > R) return -1;
        if (l >= L && r <= R) {
            if (t[x].min <= lim) return flt(x, l, r, lim);
            else return -1;
        }
        int mid = (l + r) / 2, res = fl(x * 2 + 1, mid + 1, r, L, R, lim);
        if (~res) return res;
        return fl(x * 2, l, mid, L, R, lim);
    }
    int fl(int l, int r, int lim) {return fl(1, 1, n, l, r, lim);}
} seg;

int ans;
void solve(int l, int r) {
    if (l >= r) return ;
    int val = a[(l + r) / 2];
    while (true) {
        int lp = seg.ff(l, r, val);
        int rp = seg.fl(l, r, val);
        if (lp >= rp) {
            solve(l, rp);
            solve(rp + 1, r);
            break;
        }
        std::swap(a[lp], a[rp]);
        ++ans;
        seg.modify(lp, a[lp]);
        seg.modify(rp, a[rp]);
    }
}

void solve() {
    std::cin >> n;
    for (int i = 1; i <= n; ++i) std::cin >> a[i];
    ans = 0;
    seg.build(1, 1, n);
    solve(1, n);
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) solve();    

    return 0;
}

answer.code:115:1: fatal error: error writing to /tmp/cc6Hp5F0.s: File too large
  115 | }
      | ^
compilation terminated.