#include "bits/stdc++.h"

#define fastio ios::sync_with_stdio(0), cin.tie(nullptr)

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using tiii = tuple<int,int,int>;

struct SegTree {
    vector<pii> seg_l, seg_r;
    int lr_start;
    int lr_size = 1;

    SegTree(vector<int> &a) {
        setSize(a.size());

        lr_start = seg_l.size() - lr_size;

        for(int i = 0; i < a.size(); i++) {
            seg_l[lr_start + i] = {a[i],i};
            seg_r[lr_start + i] = {a[i],i};
        }

        for(int i = lr_start-1; 0 <= i; i--) {
            seg_r[i] = max(seg_r[2*i+1], seg_r[2*i+2]);
            if(seg_l[2*i+1].first == seg_l[2*i+2].first) seg_l[i] = min(seg_l[2*i+1], seg_l[2*i+2]);
            else seg_l[i] = max(seg_l[2*i+1], seg_l[2*i+2]);
        }
    }

    void setSize(int array_size) {
        while(lr_size < array_size) lr_size *= 2;
        seg_l.resize(2*lr_size - 1, {INT_MIN, -1});
        seg_r.resize(2*lr_size - 1, {INT_MIN, -1});
    }

    pii query_r(int l, int r, int lx = 0, int rx = -1, int i = 0) {
        if(rx == -1) rx = lr_size-1;

        int m = (lx+rx)/2;

        if(rx < l || r < lx) return {INT_MIN, -1};
        if(l <= lx && rx <= r) return seg_r[i];
        return max(query_r(l, r, lx, m, 2*i+1), query_r(l, r, m+1, rx, 2*i+2));
    }

    pii query_l(int l, int r, int lx = 0, int rx = -1, int i = 0) {
        if(rx == -1) rx = lr_size-1;

        int m = (lx+rx)/2;

        if(rx < l || r < lx) return {INT_MIN, -1};
        if(l <= lx && rx <= r) return seg_l[i];

        pii lc = query_l(l, r, lx, m, 2*i+1), rc = query_l(l, r, m+1, rx, 2*i+2);
        if(lc.first == rc.first) return min(lc, rc);
        return max(lc, rc);
    }
};

void turn_on(int s, int e, SegTree &seg, vector<int> &p, vector<bool> &on) {
    if(s+1 == e) return;
    auto [best_mid_l, i_l] = seg.query_l(s+1, e-1);
    auto [best_mid_r, i_r] = seg.query_r(s+1, e-1);

    if(best_mid_r < p[s] && best_mid_r < p[e] || best_mid_r == min(p[s],p[e])) return;
    
    int new_on_i;
    if(p[s] < p[e]) new_on_i = i_l;
    else new_on_i = i_r;

    on[new_on_i] = true;

    turn_on(s, new_on_i, seg, p, on);
    turn_on(new_on_i, e, seg, p, on);
}

int main() {
    fastio;

    int t;
    cin >> t;

    while(t--) {
        int n;
        cin >> n;

        vector<int> p(n);
        for(int &pi : p) cin >> pi;

        vector<bool> on(n, false);
        on[0] = on[n-1] = true;

        SegTree seg(p);

        turn_on(0, n-1, seg, p, on);

        ll ans = 0;

        for(int i = 0, counter = 0; i < n; i++, counter++) {
            if(on[i]) {
                ans += counter * ll(p[i]);
                counter = 0;
            }
        }
        for(int i = n-1, counter = 0; i >= 0; i--, counter++) {
            if(on[i]) {
                ans += counter * ll(p[i]);
                counter = 0;
            }
        }

        cout << ans << '\n';
    }
}