#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n; cin >> n;
    vector<int> p(n); for(int& v : p) cin >> v;
    vector<int> stk = {n-1};
    auto bad = [&](int i, int j, int k){
        // (i,p[i]), etc
        int ax = j-i, ay = p[j]-p[i], bx = k-i, by = p[k]-p[i];
        return 1ll*ax*by - bx*ay <= 0;
    };
    for(int i = n-2; i >= 0; i--){
        while(stk.size() >= 2 && bad(stk[stk.size()-2],stk.back(),i)) stk.pop_back();
        stk.push_back(i);
    }
    int64_t ans = 0;
    for(int i = 0; i+1 < (int)stk.size(); i++){
        ans += 1ll*(p[stk[i]]+p[stk[i+1]])*(stk[i]-stk[i+1]);
    }
    cout << ans << "\n";
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    while(t--) solve();
}
// if we choose bars i_1,i_2,...,i_k,
// then the answer is (p_{i_1}+p_{i_2})(i_2-i_1)+(p_{i_2}+p_{i_3})(i_3-i_2) + ...
// equal to the sum of trapezoid areas between points