#include "bits/stdc++.h"

using namespace std;
using lint = int64_t;

using num = int64_t;
struct frac {
    num n, d;
    frac() : n(0), d(1) { }
    frac(num _n, num _d = 1) : n(_n), d(_d) {
        num g = gcd(n, d); n /= g, d /= g;
        if(d < 0) n *= -1, d *= -1;
        assert(d != 0);
    }
    friend bool operator<(const frac &l, const frac &r) {
        return __int128(1) * l.n * r.d < __int128(1) * r.n * l.d;
    }
    friend frac operator+(const frac &l, const frac &r) {
        num g = gcd(l.d, r.d);
        return frac(r.d / g * l.n + l.d / g * r.n, l.d/g * r.d);
    }
};

struct Line {
    mutable lint k, m, c;
    mutable frac p;
    bool operator<(const Line &o) const {return k < o.k; }
    bool operator<(frac x) const {return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
    static const lint inf = LLONG_MAX;
    frac div(lint a, lint b) {
        return frac(a, b);
    }
    bool isect(iterator x, iterator y) {
        if(y == end()) { x->p = frac(inf, 1); return false;}
        if(x->k == y->k) x->p = x->m > y->m ? frac(inf, 1) : frac(-inf, 1);
        else x->p = div(y->m - x->m, x->k - y->k);
        return !(x->p < y->p);
    }
    void add(lint k, lint m, lint c) {
        auto z = insert({k, m, c, frac(0, 1)}), y = z++, x = y;
        while(isect(y, z)) z = erase(z);
        if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while((y = x) != begin() && !((--x)->p < y->p) )
            isect(x, erase(y));
    }
    lint query(lint x, lint y) {
        assert(!empty());
        auto l = *lower_bound(frac(x, y));
        cout<<l.k<<" "<<l.m<<" "<<l.c<<"\n";
        return l.k * x + l.m * y + l.c;
    }
};




int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<lint>p(n+2);
        for(int i=1;i<=n;i++) cin>>p[i];
        vector<int>left(1), right(1, n+1);

        for(int i=1;i<=n;i++){
            if(p[i] > p[left.back()]) left.push_back(i);
        }
        for(int i=n;i>=1;i--){
            if(p[i] > p[right.back()]) right.push_back(i);
        }
        reverse(right.begin(), right.end());
        for(int u : right) left.push_back(u);
        int m = int(size(left));

        vector<int>ind(m);
        iota(ind.begin(), ind.end(), 0);
        sort(ind.begin(), ind.end(), [&](int i, int j){
            return p[i] > p[j];
        });
        set<int>s;
        s.insert(0);
        s.insert(n + 1);
        lint ans = 0;
        for(int i=0;i<m;i++){
            int j = ind[i];
            auto it = s.lower_bound(j);
            int l = *prev(it), r = *it;
            lint cur = (min(n, r) - max(1, l)) * (p[l] + p[r]);
            lint nxt = (min(n, r) - j) * (p[r] + p[j]) + (j - max(1, l)) * (p[j] + p[l]);
            //cout<<nxt<<" "<<cur<<" "<<j<<"\n";
            if(nxt > cur){
                ans += nxt - cur;
                s.insert(j);
            }
        }    
        cout<<ans<<"\n";    
    }
    return 0;
}