#include <bits/stdc++.h>

#define gc() getchar()
template <typename T> inline void rd(T& x) {
	int si = 1; char c = gc(); x = 0;
	while(!isdigit(c)) si = c == '-' ? -1 : si, c = gc();
	while(isdigit(c)) x = x * 10 + c - 48, c = gc();
	x *= si;
}
template <typename T, typename... Args>
inline void rd(T& x, Args&... args) { rd(x); rd(args...); }
#define fi first
#define se second
#define mkp std::make_pair
typedef unsigned ui;
typedef long long ll;
typedef unsigned long long ull;
typedef double ff;
typedef std::pair <int, int> pii;
const int N = 5e5 + 5, INF = 0x3f3f3f3f;

int n, ans, p[N], q[N];

void Swap(int i, int j) {
	std::swap(p[i], p[j]);
	std::swap(q[p[i]], q[p[j]]);
	++ans;
}
int Partition(int l, int r) {
	int mid = p[(l + r) / 2];
	std::vector <int> a, b;
	if(mid < (l + r) / 2) {
		for(int i = l; i <= mid; ++i)
			if(p[i] > mid) a.push_back(i);
		for(int i = l; i < mid; ++i)
			if(q[i] >= mid) b.push_back(q[i]);
	} else {
		for(int i = mid; i <= r; ++i)
			if(p[i] < mid) b.push_back(i);
		for(int i = mid + 1; i <= r; ++i)
			if(q[i] <= mid) a.push_back(q[i]);
	}
	std::sort(a.begin(), a.end());
	std::sort(b.rbegin(), b.rend());
	a.push_back(INF); b.push_back(-INF);
	int i = l - 1, j = r + 1, _i = 0, _j = 0;
	while(true) {
		++i; --j;
		while(a[_i] < i) ++_i;
		while(b[_j] > j) ++_j;
		i = std::min(a[_i], q[mid] >= i ? q[mid] : INF);
		j = std::max(b[_j], q[mid] <= j ? q[mid] : -INF);
		if(i >= j)
			return q[mid] <= mid ? mid : mid - 1;
		Swap(i, j);
	}
}
void QuickSort(int l, int r) {
	if(l < r) {
		int pos = Partition(l, r);
		QuickSort(l, pos);
		QuickSort(pos + 1, r);
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int test_case_cnt = 1; rd(test_case_cnt);
	while(test_case_cnt--) {
		ans = 0;
		rd(n);
		for(int i = 1; i <= n; ++i) {
			rd(p[i]); q[p[i]] = i;
		}
		QuickSort(1, n);
		printf("%d\n", ans);
	} return 0;
}