#include <bits/stdc++.h>
using namespace std;

int ilwekt(pair<int, int> X, pair<int, int> Y, pair<int, int> Z){
    int x1 = Z.first - X.first, y1 = Z.second - X.second;
    int x2 = Y.first - X.first, y2 = Y.second - X.second;
    return x1*y2 - x2*y1;
}

stack<int> otoczka(vector<int> &B){
    stack<int> S;
    S.push(0);
    int x = 0, y = 1;
    for(int i = 2; i<B.size(); i++){
        while(ilwekt({x, B[x]}, {y, B[y]}, {i, B[i]})<0){
            y = x;
            S.pop();
            if(S.empty()) break;
            x = S.top();
        }
        S.push(y);
        x = y;
        y = i;
    }
    S.push(B.size()-1);
    return S;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int z;
    cin >> z;
    while(z--){
        int n;
        cin >> n;
        vector<int> B(n);
        for(auto &b : B) cin >> b;
        auto S = otoczka(B);
        int ans = 0;
        int lp = 0, lr = 0;
        for(int i = n-1; i>=0; i--){
            if(i==S.top()){
                ans+=lr*B[i];
                S.pop();
                if(S.empty()) break;
                lp = i-S.top();
                ans+=lp*B[i];
                lr = i-S.top();
            }
        }
        cout << ans << "\n";
    }
    return 0;
}