#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()

const int N = 5e5 + 5;
ll a[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // for (int i = 1; i <= n; i++) {
    //     dp[i] = (i - 1) * a[i]; 
    //     for (int j = 1; j < i; j++)
    //         dp[i] = max(dp[i], dp[j] + (i - j) * (a[i] + a[j]));
    // }
    // ll ans = 0;
    // for (int i = 1; i <= n; i++)
    //     ans = max(ans, dp[i] + (n - i) * a[i]);
    // cout << ans << "\n";
    vector<ll> L;
    L.pb(1);
    for (int i = 2; i <= n; i++)
        if (a[i] > a[L.back()])
            L.pb(i);
    vector<ll> R;
    R.pb(n);
    for (int i = n - 1; i >= 1; i--)
        if (a[i] > a[R.back()])
            R.pb(i);
    reverse(ALL(R));
    for (int x : R)
        if (x > L.back())
            L.pb(x);
    ll ans = 0;
    for (int i = 0; i + 1 < SZ(L); i++) {
        ans += (a[L[i]] + a[L[i + 1]]) * (L[i + 1] - L[i]);
    }
    ans += a[L[0]] * (L[0] - 1);
    ans += a[L.back()] * (n - L.back());
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
}