#include<bits/stdc++.h>
using namespace std;
using Int = long long;
using uInt = unsigned long long;
#define lowbit(x)  ((x) & - (x))
using ll = long long;
void update(vector<int>& tr, int x, ll v) {      // 单点修改(加)
	for (; x < tr.size(); x += lowbit(x))
		tr[x] += v;
}
ll qr(vector<int>& tr, int x) {                     //前缀查询
	ll sum = 0;
	for (x; x >= 1; x -= lowbit(x)) sum += tr[x];
	return sum;
}
ll query(vector<int>& tr, int l, int r) {            //区间查询
	return qr(tr, r) - qr(tr, l - 1);
}
bool cmp(pair<int, int>& p1,pair<int, int>& p2) {
	if (p1.first != p2.first)return p1.first > p2.first;
	return p1.second < p2.second;
}
void solve() {
	int n; cin >> n;
	vector<int>v(n + 1),cnt;
	cnt.push_back(0);
	for (int u = 1; u <= n; ++u)cin >> v[u], cnt.push_back(v[u]);
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end())-v.begin());	
	for (int u = 1; u <= n; ++u)
		cnt[u] = lower_bound(v.begin(), v.end(), cnt[u]) - v.begin();
	vector<pair<int, int>>vp(n + 1);
	for (int u = 1; u <= n; ++u)vp[u].first = cnt[u], vp[u].second = u;
	sort(vp.begin()+1, vp.end(),cmp);
	vector<int>is(n+1);
	Int ans = 0;
	for (int u = 1; u <= n; ++u) {
		int l =0, r = vp[u].second;
		while (l + 1 < r) {
			int mid = l + r >> 1;
			int sum = query(is, mid, vp[u].second);
			if (sum>1) {
				l = mid + 1;
			}
			else if(sum==0) {
				r = mid;
			}
			else {
				l = mid;
			}
		}
		ans += (vp[u].second - 1 - l);
		if (u==n|| vp[u].first != vp[u + 1].first) {
			if (query(is, vp[u].second, n) != 0) {
				int l = vp[u].second + 1, r = n + 1;
				while (l + 1 < r) {
					int mid = l + r >> 1;
					int sum = query(is, vp[u].second, mid);
					if (sum > 1) {
						r = mid;
					}
					else if (sum == 0) {
						l = mid + 1;
					}
					else {
						l = mid;
					}
				}
				ans += (l-1-vp[u].second);
			}
		}
		update(is, vp[u].second, 1);
	}
	cout << ans << endl;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	for(int i=1,n=(cin>>n,n);i<=n;++i)
		solve();
	return 0;
}