#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,m,a[maxn],T,pos[maxn],sum,b[maxn];
bool cmp(int x,int y){return x>y;}
void solve(int l,int r){
    if(l>=r||l<=0||r>n)return ;
    int x=a[(l+r)/2];
    int p;
    //cout<<l<<" "<<r<<" "<<x<<endl;
    if(x-l+1<r-x){
        int cnt=0;
        for(int i=l;i<=x;i++){
            b[++cnt]=pos[i];
        }
        sort(b+1,b+cnt+1);
        int L=l-1,R=r+1,id=l;
        //cout<<L<<" "<<R<<endl;
        while(L<=R){
            L++;
            while(a[L]<x&&L<=r)L++;
            R=b[cnt];
            if(!cnt){p=L-1;break;}
            if(L>=R){p=R;break;}
            swap(a[L],a[R]);
            pos[a[L]]=L,pos[a[R]]=R;
            sum++;cnt--;
        }

        //cout<<p<<endl;
    }
    else{
        int cnt=0;
        for(int i=x;i<=r;i++){
            b[++cnt]=pos[i];
        }
        sort(b+1,b+cnt+1,cmp);
        int L=l-1,R=r+1,id=l;
        //cout<<L<<" "<<R<<endl;
        while(L<=R){

            L=b[cnt];
            R--;
            while(a[R]>x&&R>=l)R--;
            
            if(!cnt){p=R;break;}
            if(L>=R){p=R;break;}
            swap(a[L],a[R]);
            pos[a[L]]=L,pos[a[R]]=R;
            cnt--;sum++;
            
        }//cout<<p<<endl;
    }
    solve(l,p),solve(p+1,r);
}
void SSolve(){
    scanf("%d",&n);sum=0;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i;
    solve(1,n);
    printf("%d\n",sum);
}
signed main(){
    scanf("%d",&T);
    while(T--){
        SSolve();
    }
}