#include<bits/stdc++.h>
#define N 500010
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
int rd() {
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
	return res*f;
}
int Tim,n,a[N];
struct Seg {
	int mn[N<<2],mx[N<<2];
	void update(int p) {
		mn[p]=min(mn[p<<1],mn[p<<1|1]);
		mx[p]=max(mx[p<<1],mx[p<<1|1]);
	}
	void build(int p,int l,int r) {
		if(l==r) {mn[p]=mx[p]=a[l];return ;}
		int mid=l+r>>1;
		build(p<<1,l,mid),build(p<<1|1,mid+1,r);
		update(p);
	}
	void modify(int p,int l,int r,int x) {
		if(l==r) {mn[p]=mx[p]=a[x];return ;}
		int mid=l+r>>1;
		if(x<=mid) modify(p<<1,l,mid,x);
		else modify(p<<1|1,mid+1,r,x);
		update(p);
	}
	int findl(int p,int l,int r,int L,int R,int v) {
		if(mx[p]<v) return -1;
		if(l==r) return l;
		int mid=l+r>>1;
		if(R<=mid) return findl(p<<1,l,mid,L,R,v);
		if(L>mid) return findl(p<<1|1,mid+1,r,L,R,v);
		int tmp=findl(p<<1,l,mid,L,R,v);
		if(tmp!=-1) return tmp;
		return findl(p<<1|1,mid+1,r,L,R,v);
	}
	int findr(int p,int l,int r,int L,int R,int v) {
		if(mn[p]>v) return -1;
		if(l==r) return l;
		int mid=l+r>>1;
		if(R<=mid) return findr(p<<1,l,mid,L,R,v);
		if(L>mid) return findr(p<<1|1,mid+1,r,L,R,v);
		int tmp=findr(p<<1|1,mid+1,r,L,R,v);
		if(tmp!=-1) return tmp;
		return findr(p<<1,l,mid,L,R,v);
	}
}T;
int ans;
void solve(int l,int r) {
	if(l==r) return ;
	int p=l+r>>1;
	int L=l,R=r,A,B;
	while(L!=p||R!=p) {
		A=L!=p?T.findl(1,1,n,L,p,a[p]):p;
		B=R!=p?T.findr(1,1,n,p,R,a[p]):p;
		L=A,R=B;
		if(L==R) break;
		if(p==L) p=R;
		else if(p==R) p=L;
		swap(a[L],a[R]),T.modify(1,1,n,L),T.modify(1,1,n,R),ans++;
	}
	if(p>l) solve(l,p-1);
	if(p<r) solve(p+1,r);
}
int main() {
	Tim=rd();
	while(Tim--) {
		n=rd();
		rep(i,1,n) a[i]=rd();
		T.build(1,1,n);
		ans=0,solve(1,n);
		printf("%d\n",ans);
	}
	return 0;
}