#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		vector<ll> v(n);
		for(auto &d:v) cin >> d;
		vector<int> st;
		// Optimal solution assuming bars 0 and i are the leftmost and rightmost bars
		for(int i=0; i<n; i++){
			while(st.size() >= 2){
				ll keep = v[end(st)[-1]] * (i - end(st)[-2]);
				keep += v[end(st)[-2]] * (end(st)[-1] - end(st)[-2]);
				keep += v[i] * (i - end(st)[-1]);
				
				ll rmv = v[end(st)[-2]] * (i - end(st)[-2]);
				rmv += v[i] * (i - end(st)[-2]);
				
				// cout << "at bar " << i << endl;
				// cout << "stack: ";
				// for(int d:st) cout << d << ' ';
				// cout << endl;
				// cout << "keep: " << keep << endl;
				// cout << "rmv: " << rmv << endl;
				
				if(rmv >= keep) st.pop_back();
				break;
			}
			st.push_back(i);
		}
		int m = st.size();
		
		// cout << "stack: ";
		// for(int d:st) cout << d << ' ';
		// cout << endl;
		
		ll ans = v[st[0]] * (st[1] - st[0]);
		ans += v[end(st)[-1]] * (end(st)[-1] - end(st)[-2]);
		for(int i=1; i+1<m; i++){
			ans += v[st[i]] * (st[i+1] - st[i-1]);
		}
		cout << ans << endl;
	}
}