#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];

int v[MAXN];

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(0);
	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);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> v[i];
		}
		build(1, 1, n);
		ll ans = 0;
		vector<int> get = {1, n};
		int ini = 1, fim = n;
		while (true) {
			// cout << ini << ' ' << fim << endl;
			int tam = fim - ini - 1;
			if (tam == 0) break;
			no at = query(1, 1, n, ini + 1, fim - 1);
			if (at.mx <= min(v[ini], v[fim])) {
				break;
			}
			else if (at.mx > min(v[ini], v[fim]) && at.mx <= max(v[ini], v[fim])) {
				if (v[ini] >= v[fim]) {
					get.push_back(at.posLast);
					fim = at.posLast;
				}
				else {
					get.push_back(at.posFirst);
					ini = at.posFirst;
				}
			}
			else {
				get.push_back(at.posFirst);
				ini = at.posFirst;
			}
		}
		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 << '\n';
		cout << ans << '\n';
	}
    return 0;
}