#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int maxn = 500050;

ll ans;
int n;
int pi[maxn];
pair<int,int>ai[maxn];

void go(int l,int r,int i)
{
	if(i>n || ( pi[l]>=ai[i].first && pi[r]>=ai[i].first ) ) return;
	int pos= ai[i].second;
	if(pos<=l||pos>=r) go(l,r,i+1);
	
	ll temp= 1ll*(pos-l)*(ai[i].first-pi[r])+ 1ll*(r-pos)*(ai[i].first-pi[l]);
	if(temp<=0) go(l,r,i+1);
	else
	{
		ans+=temp;
		go(l,pos,i+1);
		go(pos,r,i+1);
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n;
		for(int i=1;i<=n;i++) 
		{
			cin>>pi[i];
			ai[i]=make_pair(pi[i],i);
		}
		sort(ai+1,ai+n+1,greater< pair<int,int> >());
		
		ans=1ll*(n-1)*(pi[1]+pi[n]);
		
		go(1,n,1);
		
		cout<<ans<<endl;
	}
	
	return 0;
}