https://qoj.ac/contest/1794/problem/9313
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int N=2e5+10,mod=1e9+7;
ll n,m,q;
int a[N],stk[N],tt;
int l[N],r[N];
ll res;
void build()//构建笛卡尔树
{
memset(l,0,sizeof l);
memset(r,0,sizeof r);
tt=0;
int top=tt;
for(int i=1;i<=n;i++)
{
while(tt>0&&a[stk[tt-1]]<a[i]) tt--;
if(tt) r[stk[tt-1]]=i;
if(tt!=top) l[i]=stk[tt];
stk[tt++]=i;
top=tt;
}
}
void dfs(int u,int dep)//每个数加上左边和右边比它小的数（连续且之间不能用大于等于它的数）
{
res+=dep;
if(l[u]) dfs(l[u],dep+(a[l[u]]!=a[u]));
if(r[u]) dfs(r[u],dep+(a[r[u]]!=a[u]));
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
build();
res=0;
dfs(stk[0],0);
cout<<res<<endl;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _;
cin>>_;
while(_--)
{
solve();
}
return 0;
}