#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 500010;
int n, a[N], ans;
int mn[N * 4], mx[N * 4];

void pushup(int u) {
	mn[u] = min(mn[u * 2], mn[u * 2 + 1]);
	mx[u] = max(mx[u * 2], mx[u * 2 + 1]);
}
void build(int u, int l, int r) {
	if(l >= r) { mn[u] = mx[u] = a[l]; return ; }
	int mid = (l + r) >> 1;
	build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
	pushup(u);
}
void mdy(int u, int l, int r, int x) {
	if(l >= r) { mn[u] = mx[u] = a[l]; return ; }
	int mid = (l + r) >> 1;
	x <= mid ? mdy(u * 2, l, mid, x) : mdy(u * 2 + 1, mid + 1, r, x);
	pushup(u);
}
int findl(int u, int l, int r, int L, int R, int w) {
	if(mx[u] < w || R < l || L > r) return 0;
	if(l >= r) return l;
	int mid = (l + r) >> 1;
	int res = 0;
	if(L <= mid) res = findl(u * 2, l, mid, L, R, w);
	if(res) return res;
	if(R > mid) res = findl(u * 2 + 1, mid + 1, r, L, R, w);
	return res;
}
int findr(int u, int l, int r, int L, int R, int w) {
	if(mn[u] > w || R < l || L > r) return 0;
	if(l >= r) return l;
	int mid = (l + r) >> 1;
	int res = 0;
	if(R > mid) res = findr(u * 2 + 1, mid + 1, r, L, R, w);
	if(res) return res;
	if(L <= mid) res = findr(u * 2, l, mid, L, R, w);
	return res;
}
void qsort(int l, int r) {
	if(l >= r) return ;
	int mid = a[(l + r) / 2], pos = (l + r) / 2;
	int tl = l, tr = r;
	for(;;) {
		tl = findl(1, 1, n, tl, r, mid);
		tr = findr(1, 1, n, l, tr, mid);
//		printf(">>> %d %d : %d %d\n", l, r, tl, tr);
		assert(tl && tr);
		if(tl >= tr) { pos = tl; break; }
		swap(a[tl], a[tr]), ++ans;
		mdy(1, 1, n, tl), mdy(1, 1, n, tr);
	}
	qsort(l, pos), qsort(pos + 1, r);
}
void solve() {
	scanf("%d", &n), ans = 0;
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	build(1, 1, n);
	qsort(1, n);
	printf("%d\n", ans);
}
int main() {
	int T; scanf("%d", &T);
	for(; T; --T) solve();
	return 0;
}