#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;


void solve(){
	int n;
	cin >> n;
	vector<int> a(n+1);
	a[0] = a[n+1] = 2e9;
	for(int i = 1;  i<= n; i++)cin >> a[i];
	long long ans = 0;
	vector<int> stk{0};
	for(int i = 1; i <= n; i++){
		while(!stk.empty() && a[stk.back()]<a[i])stk.pop_back();
		ans += i - stk.back()-1;
		cout << ans <<endl;
		stk.push_back(i);
	}
	stk.clear();
	stk.push_back(n+1);
	for(int i = n; i >= 1; i--){
		while(!stk.empty() && a[stk.back()]<a[i])stk.pop_back();
		if(a[stk.back()]!=a[i])
		ans +=stk.back()- i  -1;
		//cout <<ans <<endl;
		stk.push_back(i);
	}
	cout << ans <<endl;
}


int main() {
	int t;
	cin >> t;
	while(t--){
		solve();
	}
	return 0;
}