#include<iostream>
#include<cstdio>
using namespace std;
const int MX=500050;
const int inf=0x3fffffff;

int T, N, num=0;
int br[MX], ar[MX];
int tm[4*MX], tp[4*MX];
int read()
{
    int r=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
    return r*f;
}
void bt(int n, int s, int e)
{
    if(s==e) {tm[n]=tp[n]=ar[s]; return;}
    int mid=(s+e)>>1, ln=2*n, rn=2*n+1;
    bt(ln,s,mid); bt(rn,mid+1,e);
    tm[n]=min(tm[ln],tm[rn]);
    tp[n]=max(tp[ln],tp[rn]);
}
void upd(int n, int s, int e, int p, int v)
{
    if(s==e) {tm[n]=tp[n]=v; return;}
    int mid=(s+e)>>1, ln=2*n, rn=2*n+1;
    if(p<=mid) upd(ln,s,mid,p,v);
    else upd(rn,mid+1,e,p,v);
    tm[n]=min(tm[ln],tm[rn]);
    tp[n]=max(tp[ln],tp[rn]);    
}
int ask(int n, int s, int e, int L, int R, int v, int tpe)
{
    if(s>R||e<L) return tpe*inf;
    if(s>=L&&e<=R)
    {
        if(tpe==1)
        {
            if(tp[n]<v) return inf;
            if(s==e) return s;
            int mid=(s+e)>>1, ln=2*n, rn=2*n+1;
            if(tp[ln]>=v) return ask(ln,s,mid,L,R,v,tpe);
            else return ask(rn,mid+1,e,L,R,v,tpe);
        }
        if(tpe==-1)
        {
            if(tm[n]>v) return -inf;
            if(s==e) return s;
            int mid=(s+e)>>1, ln=2*n, rn=2*n+1;
            if(tm[rn]<=v) return ask(rn,mid+1,e,L,R,v,tpe);
            else return ask(ln,s,mid,L,R,v,tpe);
        }
    }
    int mid=(s+e)>>1, ln=2*n, rn=2*n+1;
    if(tpe==1)
    {
        return min(ask(ln,s,mid,L,R,v,tpe),ask(rn,mid+1,e,L,R,v,tpe));
    }
    else if(tpe==-1)
    {
        return max(ask(ln,s,mid,L,R,v,tpe),ask(rn,mid+1,e,L,R,v,tpe));
    }
}
int part(int a[], int lo, int hi)
{
    int pivot=a[(lo+hi)/2];
    int i=lo-1, j=hi+1;
    while(1)
    {
        i=ask(1,1,N,i+1,N,pivot,1); //tpe=1, first >=
        j=ask(1,1,N,1,j-1,pivot,-1); //tpe=1, first <=
        // cout << "i=" << i << ", j=" << j << '\n';
        if(i>=j) 
        {
            // cout << "lo=" << lo << ", hi=" << hi << ", j=" << j << '\n';
            return j;
        }
        upd(1,1,N,j,a[i]);
        upd(1,1,N,i,a[j]);
        swap(a[i],a[j]);
        num++;
    }
}
void qsort(int a[], int lo, int hi)
{
    if(lo>=0&&hi>=0&&lo<hi)
    {
        int p=part(a,lo,hi);
        // for(int i=1;i<=N;i++) cout << a[i] << " "; cout << '\n';
        qsort(a,lo,p);
        qsort(a,p+1,hi);
    }
}
int main()
{
    // freopen("testdata.in","r",stdin);
    T=read();
    while(T--)
    {
        N=read(); num=0;
        for(int i=1;i<=N;i++) ar[i]=read();
        bt(1,1,N);
        qsort(ar,1,N);
        cout << num << '\n';
    }
    return (0-0);
}