#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);
    }

    int findFirstUpper(int p, int l, int r, int x, int y, int v) { // 向右找第一个不小于v的值
        if (tr[p].mx < v) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int mid = (l + r - 1) / 2;
        if (x > mid) {
            return findFirstUpper(2 * p + 1, m, r, x, y, v);
        }
        int ret = findFirstUpper(2 * p, l, m, x, y, v);
        if (ret != -1) {
            return ret;
        }
        return findFirstUpper(2 * p + 1, m, r, x, y, v);
    }

    int findFirstLower(int p, int l, int r, int x, int y, int v) { //向左找第一个不大于v的值
        if (tr[p].mn > v) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        if (m > x) {
            return findFirstLower(2 * p, l, m, x, y, v);
        }
        int ret = findFirstLower(2 * p + 1, m, r, x, y, v);
        if (ret != -1) {
            return ret;
        }
        return  findFirstLower(2 * p, l, m, x, y, v);
    }

    int findFirstUpper(int l, int r, int v) {
        return findFirstUpper(1, 0, n, l, r, v);
    }
    int findFirstLower(int l, int r, int v) {
        return findFirstLower(1, 0, n, l, r, v);
    }
#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));
    }
};

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--;
        if (j - i + 1 <= 15) {
            while (a[i] < m) i++;
            while (a[j] > m) j--;
        }
        else {
            std::tie(i, j) = std::pair(seg.findFirstUpper(i, j + 1, m), seg.findFirstLower(i, j + 1, m));
        }
        if (i >= j) {
            return j;
        }
        else {
            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);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[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;
}