#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n;
int a[N];
struct A {
	int mx, mn;
} tree[N * 8];

void updata(int now) {
	tree[now].mx = max(tree[now * 2].mx, tree[now * 2 + 1].mx);
	tree[now].mn = min(tree[now * 2].mn, tree[now * 2 + 1].mn);
}
void bd(int now,int ll,int rr)
{
	if(ll==rr)
	{
		tree[now].mx=tree[now].mn=a[ll];
		return;
	}
	int mid=(ll+rr)/2;
	bd(now*2,ll,mid);
	bd(now*2+1,mid+1,rr);
	updata(now);
}
void change(int x, int num, int now, int ll, int rr) {
	if (x < ll || rr < x)return;
	if (ll == rr && ll == x) {
		tree[now].mx = tree[now].mn = num;
		return;
	}
	int mid = (ll + rr) / 2;
	change(x, num, now * 2, ll, mid);
	change(x, num, now * 2 + 1, mid + 1, rr);
	updata(now);
	return;
}
int findl(int num, int now, int ll, int rr, int l, int r) {
	if (ll > r || l > rr)return 0;
	if (tree[now].mx < num) return 0;
	if (ll == rr) {
		return ll;
	}
	int mid = (ll + rr) / 2;
	int tmp = findl(num, now * 2, ll, mid, l, r);
	if (tmp) return tmp;
	return findl(num, now * 2 + 1, mid + 1, rr, l, r);
}
int findr(int num, int now, int ll, int rr, int l, int r) {
	if (ll > r || l > rr)return 0;
	if (tree[now].mn > num) return 0;
	if (ll == rr) {
		return ll;
	}
	int mid = (ll + rr) / 2;
	int tmp = findr(num, now * 2 + 1, mid + 1, rr, l, r);
	if (tmp) return tmp;
	return findr(num, now * 2, ll, mid, l, r);
}
long long st(int l,int r)
{
	//cout<<l<<' '<<r<<endl;
	if(l>=r)return 0;
	long long tot=0;
	int mid=(l+r)/2;
	int ll=l,rr=r,pivot=a[mid];
	int sp=0;
	while(1)
	{
		int tol=findl(pivot,1,1,n,ll,n);
		int tor=findr(pivot,1,1,n,1,rr);
		if(tol>=tor)
		{
			sp=tor;	
			break;
		}
		change(tol,a[tor],1,1,n);
		change(tor,a[tol],1,1,n);
		swap(a[tol],a[tor]);
		tot++;
		ll=tol+1,rr=tor-1;
		
		if(ll>=rr) 
		{
			sp=rr;
			break;
		}
	}
	tot+=st(l,sp);
	tot+=st(sp+1,r);
	return tot;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		bd(1,1,n);
		long long ans=st(1,n);
		cout<<ans<<'\n';
	}






	return 0;
}