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

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

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

    int findRightUpper(int x, int v) {
        return findRightUpper(1, 0, n, x, v);
    }
    int findLeftLower(int x, int v) {
        return findLeftLower(1, 0, n, x, 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 <= 10) {
            while (a[i] < m) i++;
            while (a[j] > m) j--;
        }
        else {
            std::tie(i, j) = std::pair(seg.findLeftLower(i, m), seg.findRightUpper(j, m));
        }

        if (i >= j) {
            return 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);
    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;
}