#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
const int N = 2e5+10, M = 1e6+10, X =2e9+10;
//
int a[N];
struct node{
	int c;
	int x,y;
	node(int cc,int xx,int yy){
		c=cc;x=xx;y=yy;
	}
};
struct cmp{
	bool operator()(const node&a,const node&b){
		if(a.c!=b.c) return a.c>b.c;
		return a.x>b.x;
	}
};
priority_queue<node,vector<node>,cmp> q;
void solve(){
	int n;
	ll ans=0;
	cin>>n;
	a[0]=X;a[n+1]=X;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	for(int i=2,l=1;i<=n+1;++i){
		if(a[i]!=a[i-1]){
			q.push(node(a[i-1],l,i-1));
			l=i;
		}
	}
	
	while(q.size()>1){
		node w1=q.top();
		//if(w1.c==X) break;
		q.pop();
		node w2=q.top();
		if(w1.c==w2.c){
			if(w1.y==w2.x){
				q.pop();
				q.push(node(w1.c,w1.x,w2.y));	
			}
			continue;
		}
		int le=a[w1.x-1],ri=a[w1.y+1],nx=w1.x,ny=w1.y,nc;
		ans+=ny-nx+1;
		if(le<=ri) {
			nc=le;--nx;
		}
		if(le>=ri){
			nc=ri;++ny;
		}
		a[w1.x]=nc;a[w1.y]=nc;
		q.push(node(nc,nx,ny));
	}
	cout<<ans<<"\n";
	
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
	int __t;
	cin>>__t;
	while(__t--){
		solve();
	}  
}