#include <bits/stdc++.h>

template<typename T, std::size_t N> std::istream& operator>>(std::istream& is, std::array<T, N>& v) { for (auto& i : v) is >> i; return is; }
template<typename T, std::size_t N> std::ostream& operator<<(std::ostream& os, std::array<T, N>& v) { for (auto& i : v) os << i << ' '; return os; }
template<typename T> std::istream& operator>>(std::istream& is, std::vector<T>& v) { for (auto& i : v) is >> i; return is; }
template<typename T> std::ostream& operator<<(std::ostream& os, std::vector<T>& v) { for (auto& i : v) os << i << ' '; return os; }
template<typename...Args> void debug(Args...args) { ((std::cerr << args << ' '), ...); std::cerr << '\n'; }
template<typename...Args> void println(Args...args) { ((std::cout << args << ' '), ...); std::cout << '\n'; }

using i64 = long long;

template <class Info>
struct SegmentTree {
#define m (l + r) / 2
    int n;
    std::vector<Info> tr;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        tr.assign(4 << std::__lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                tr[p] = { init_[l] };
                return;
            }
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }

    void pull(int p) {
        tr[p] = tr[2 * p] + tr[2 * p + 1];
    }

    void modify(int p, int l, int r, int x, const Info& v) {
        if (r - l == 1) {
            tr[p] = v;
            return;
        }
        if (x < m) {
            modify(2 * p, l, m, x, v);
        }
        else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int x, const Info& v) {
        modify(1, 0, n, x, v);
    }

    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return tr[p];
        }
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
#undef m
};

struct Info {
    int mx, mn;
    Info(int x) :mx(x), mn(x) {}
    Info() :mx(-1e9), mn(1e9) {}
    Info(int mx, int mn) :mx(mx), mn(mn) {}
    friend Info operator+(const Info& a, const Info& b) {
        return Info(std::max(a.mx, b.mx), std::min(a.mn, b.mn));
    }
};

constexpr int N = 5e5;
int maple[N];

SegmentTree<Info> seg;

int res = 0;

int work(std::vector<int>& a, int l, int r) {
    int m = a[(l + r) / 2];
    int i = l - 1, j = r + 1;
    while (true) {
        i++, j--;
        auto work1 = [&]() {
            int lo = i, hi = a.size() - 1;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (seg.rangeQuery(i, mid + 1).mx >= m) {
                    hi = mid;
                }
                else {
                    lo = mid + 1;
                }
            }
            return lo;
        };
        auto work2 = [&]() {
            int lo = 1, hi = j;
            while (lo < hi) {
                int mid = (lo + hi + 1) / 2;
                if (seg.rangeQuery(mid, j + 1).mn <= m) {
                    lo = mid;
                }
                else {
                    hi = mid - 1;
                }
            }
            return lo;
        };
        std::tie(i, j) = std::pair(work1(), work2());

        if (i >= j) {
            return j;
        }
        else {
            auto [u, v] = std::pair(a[i], a[j]);
            seg.modify(i, a[j]);
            seg.modify(j, a[i]);
            std::swap(a[i], a[j]);
            res++;
        }
    }
    return -1;
}

void quickSort(std::vector<int>& a, int l, int r) {
    if (l >= 0 && r >= 0 && l < r) {
        int m = work(a, l, r);
        quickSort(a, l, m);
        quickSort(a, m + 1, r);
    }
}

auto solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1, -1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        a[i]--;
        maple[a[i]] = i;
    }

    seg.init(a);

    quickSort(a, 1, n);
    std::cout << res << "\n";
}

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

    int c = 1;
    std::cin >> c;

    for (int i = 1; i <= c; i++) {
        res = 0;
        solve();
    }

    return 0;
}