#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;

const int N = 5e5 + 10;
 
int n, a[N], res;
struct segtree
{
    int w1, w2;
}seg[N * 4];
 
void update(int id)
{
    seg[id].w1 = max(seg[id * 2].w1, seg[id * 2 + 1].w1);
    seg[id].w2 = min(seg[id * 2].w2, seg[id * 2 + 1].w2);
}
 
void build(int id, int l, int r)
{
    seg[id] = {0, 0};
    if(l == r)
    {
        seg[id] = {a[l], a[l]};
        return;
    }
    int mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    update(id);
}
 
void change(int id, int l, int r, int pos)
{
    if(l == r)
    {
        seg[id] = {a[l], a[l]};
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid)
        change(id * 2, l, mid, pos);
    else
        change(id * 2 + 1, mid + 1, r, pos);
    update(id);
}
 
int query1(int id, int l, int r, int val)
{
    if(l == r)
        return l;
    int mid = (l + r) >> 1;
    if(seg[id * 2].w1 >= val)
        return query1(id * 2, l, mid, val);
    else
        return query1(id * 2 + 1, mid + 1, r, val);
}
 
int query2(int id, int l, int r, int val)
{
    if(l == r)
        return l;
    int mid = (l + r) >> 1;
    if(seg[id * 2 + 1].w2 <= val)
        return query2(id * 2 + 1, mid + 1, r, val);
    else
        return query2(id * 2, l, mid, val);
}
 
int par(int l, int r)
{
    int tl = l - 1, tr = r + 1;
    int val = a[(l + r) / 2];
    while(1)
    {
        int p1 = query1(1, 1, n, val);

        int p2 = query2(1, 1, n, val);

        if(p1 >= p2)
            return p2;
        swap(a[p1], a[p2]);
        change(1, 1, n, p1);        change(1, 1, n, p2);
        res++;
        tl = p1, tr = p2;
    }   
}
void quicksort(int l, int r)
{
    if(l >= r || l < 0 || r < 0)  return;
    int p = par(l, r);
    quicksort(l, p);
    quicksort(p + 1, r);
}
 
void solve()
{       
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    res = 0;
    build(1, 1, n);
    quicksort(1, n);
    cout<<res<<'\n';
    return;
}

int main()
{
    int t;
    cin>>t;
    while(t--) solve();
}