#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<int,int>
#define piii pr<int,pii>
using namespace std;
int a[300005];
piii hd[600005];
int t;
int cv(int i,int j)
{
	return max(a[i]+j+1,a[j]+i+1);
}
ll tot;
set<pii> st;
set<pii>::iterator ls;
int n;
ll val(set<pii>::iterator x)
{
	pii g=*prev(x),h=*next(x),k=*x;
//	cout<<"Val "<<g.f<<' '<<g.s<<"  "<<k.f<<' '<<k.s<<"  "<<h.f<<' '<<h.s<<"   "<<1ll*(h.s-k.s)*(k.f-g.f)<<endl;
	return 1ll*(h.s-k.s)*(k.f-g.f);
}
void add(pii a)
{
	swap(a.f,a.s);
	int i=a.f,j=a.s;
	i=n-i;
	int fd=-1;
	ls=st.lower_bound(mp(i,-1));
	if(ls!=st.end()) fd=(*ls).s;
//	cout<<"Add "<<i<<' '<<j<<"  "<<fd<<"  "<<tot<<endl;
//	cout<<"F "<<(*ls).f<<' '<<(*ls).s<<"  "<<i<<endl;
	if(j>=fd) return;
	while(1)
	{
		ls=st.lower_bound(mp(i+1,-1));
		ls--;
		if(ls==st.begin()) break;
		if((*ls).s<j) break;
		tot-=val(ls);
		st.erase(ls);
	}
	st.insert(mp(i,j));
	tot+=val(st.find(mp(i,j)));
}
void sl()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	vector<int> e;
	t=0;
	for(int i=0;i<n;i++)
	{
		while(e.size())
		{
			if(a[e.back()]<a[i]) break;
			e.pop_back();
		}
		if(e.size()) hd[t++]=mp(e.back(),mp(cv(e.back(),i),i));
		e.push_back(i);
	}
	e.clear();
	for(int i=n-1;i>=0;i--)
	{
		while(e.size())
		{
			if(a[e.back()]<a[i]) break;
			e.pop_back();
		}
		if(e.size()) hd[t++]=mp(i,mp(cv(e.back(),i),e.back()));
		e.push_back(i);
	}
	sort(hd,hd+t);
	reverse(hd,hd+t);
	int ct=0;
	ll ans=0;
	st.clear();
	st.insert(mp(n,4*n));
	st.insert(mp(0,0));
	tot=0;
	for(int i=n-2;i>=0;i--)
	{
		for(;ct<t;ct++)
		{
			if(hd[ct].f<i) break;
			add(hd[ct].s);
		}
		ans+=4ll*n*(n-i-1)-tot;
//		cout<<"F "<<ans<<' '<<tot<<endl;
	}
	cout<<ans<<endl;
}
int main()
{
	ios_base::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--) sl();
	return 0;
}/*3
2
2 1
5
3 5 4 1 4
6
1 4 6 1 6 3
*/