#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 solve2()
{
 int maxn = 0;
	set<int> st;
	int n; cin >> n;
	vector<int>v(n + 1), cnt;
	cnt.push_back(0);
	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),maxx(n+1);
	Int ans = 0;
	for (int u = 1; u <= n; ++u) {
		int l = 0, r = vp[u].second;
		if (vp[u].second > maxx[vp[u].first]) {
			while (l + 1 < r) {
				int mid = l + r >> 1;
				int sum = query(is, mid, vp[u].second);
				if (sum) l = mid;
				else  r = mid;
			}
			ans += (vp[u].second - l - 1);
		}
			 l = vp[u].second, r = n + 1;
			while (l + 1 < r) {
				int mid = l + r >> 1;
				int sum = query(is, vp[u].second, mid);
				if (sum) r = mid;
				else l = mid;
			}
			ans += (l - vp[u].second);
			maxx[vp[u].first] = l + 1;
		update(is, vp[u].second, 1);
	}
	std::cout << ans << endl;	
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	for (int i = 1, n = (cin >> n, n); i <= n; ++i)
		solve2();
	return 0;
}