#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
    
const int MOD = 1e9 + 7;
const int MAXN = 5e5 + 5;
const ll INF = 2e18;

struct no {
	int mx, posFirst, posLast;
	no(int _mx = 0, int _posFirst = 0, int _posLast = 0) {
		mx = _mx;
		posFirst = _posFirst;
		posLast = _posLast;
	}
	no operator + (const no &x) const {
		no aux;
		if (mx == x.mx) {
			aux.mx = mx;
			aux.posFirst = min(posFirst, x.posFirst);
			aux.posLast = max(posLast, x.posLast);
		}
		else if (mx > x.mx) {
			aux = *this;
		}
		else {
			aux = x;
		}
		return aux;
	}
} a[4 * MAXN];

ll v[MAXN], n;

void build(int node, int i, int j) {
	if (i == j) {
		a[node] = no(v[i], i, i);
	}
	else {
		int m = (i + j) / 2;
		build(2 * node, i, m);
		build(2 * node + 1, m + 1, j);
		a[node] = a[2 * node] + a[2 * node + 1];
	}
}

no query(int node, int i, int j, int ini, int fim) {
	if (fim < i || j < ini) return no();
	if (ini <= i && j <= fim) return a[node];
	int m = (i + j) / 2;
	return query(2 * node, i, m, ini, fim) + query(2 * node + 1, m + 1, j, ini, fim);
}

void dfs(ll ini, ll fim, vector<ll> &get) {
	int tam = fim - ini - 1;
	if (tam == 0) return;
	no at = query(1, 1, n, ini + 1, fim - 1);
	if (at.mx <= min(v[ini], v[fim])) {
		return;
	}
	else if (at.mx > min(v[ini], v[fim]) && at.mx <= max(v[ini], v[fim])) {
		if (v[ini] >= v[fim]) {
			if ((fim - at.posLast) * v[ini] + (at.posLast - ini) * v[fim] < (fim - ini) * v[at.posLast]) {
				get.push_back(at.posLast);
				dfs(ini, at.posLast, get);
				dfs(at.posLast, fim, get);
			}
		}
		else {
			if ((at.posFirst - ini) * v[fim] + (fim - at.posFirst) * v[ini] < (fim - ini) * v[at.posFirst]) {
				get.push_back(at.posFirst);
				dfs(at.posFirst, fim, get);
				dfs(ini, at.posFirst, get);
			}
		}
	}
	else {
		get.push_back(at.posFirst);
		dfs(ini, at.posFirst, get);
		dfs(at.posFirst, fim, get);
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> v[i];
		}
		build(1, 1, n);
		ll ans = 0;
		vector<ll> get = {1, n};
		dfs(1, n, get);
		sort(get.begin(), get.end());
		for (int i = 0; i < (int)get.size(); i++) {
			// cout << get[i] << ' ';
			if (i < (int)get.size() - 1) {
				ans += v[get[i]] * (get[i + 1] - get[i]);
			}
			if (i > 0) {
				ans += v[get[i]] * (get[i] - get[i - 1]);
			}
		}
		cout << ans << '\n';
		get.clear();
	}
    return 0;
}