#include<cstdio>
#include<utility>
#include<stack>
using namespace std;

using ll = long long;
/*
const int N = 2e5+10;
ll a[N];

inline ll cm(int n){
	ll sum = 0; 
	for(int i=1;i<=n;i++)
		sum+=i;
//	cout<<"***"<<sum<<endl;
	return sum;
}

void solve(){
	stack<int>s;
	multiset<int>ss;
	ll maxx = -1; 
	ll ans = 0;
	int n; cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],maxx = max(a[i],maxx),ss.insert(a[i]);
	for(int i=1;i<=n;i++){
		if(s.empty() || s.top() == a[i]) s.push(a[i]);
		else if(a[i] == maxx&&ss.count(maxx)==1){
			ans = ans+n-1;
			while(s.size()) s.pop();
//			cout<<ans<<endl;
		}else if(a[i]>s.top()){
			ans += s.size();
			s.push(a[i]);
//			cout<<ans<<endl;
		}else if(a[i] == s.top()){
			ans += 1;
//			cout<<ans<<endl;
		}else{
			int j = i;
			s.push(a[j]);
			while(a[j]>=a[j+1]&&j<=n){
				j++;
			}
			ans = ans+cm(j-i+1);
			i = j;
//			cout<<ans<<endl;
		}
	}
	cout<<ans<<endl;}*/

using PII = pair<int,ll>;
stack<PII> sps;
inline ll op(int t){
	ll c1=0;
	ll c2=0;
	int prev=sps.top().first;
	while(sps.size() && sps.top().first<t){
		if(sps.top().first>prev){
			c2+=c1;
		}
		c1+=sps.top().second;
		printf("%d:",c1);
		prev=sps.top().first;
		sps.pop();
	}
	if(sps.size() && sps.top().first==t)sps.top().second+=c1+1;
	else sps.push({t,c1+1});
	printf("\n");
	return c1+c2;
}
void solve(){
	int n,i,t;
	scanf("%d",&n);
	scanf("%d",&t);
	sps.push({t,1});
	ll ans=0,lt=0;
	for(i=1;i<n;i++){
		scanf("%d",&t);
		if(t>sps.top().first){
			ans+=op(t);
		}else if(t==sps.top().first){
			sps.top().second+=1;
		}else{
			sps.push({t,1});
		}
	}
	while(sps.size()>1){
		lt+=sps.top().second;
		ans+=lt;
		printf("%d:",lt);
		sps.pop();
	}
	printf("%lld\n",ans);
	sps.pop();
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		solve();
	}
	return 0;
}