#include <bits/stdc++.h>

using namespace std;

struct P {
    int x, y;
    P operator-(const P& he) const {
        return {x - he.x, y - he.y};
    }
    long long operator*(const P& he) const {
        return (long long)x * he.y - (long long)he.x * y;
    }
    long long triangle(const P& a, const P& b) {
        return (a - *this) * (b - *this);
    }
};

void solve() {
    int n; cin >> n;
    vector<P> hull;
    for(int i = 1; i <= n; i++) {
        int pi; cin >> pi;
        P c{i, pi};
        while((int)hull.size() >= 2) {
            P a = hull.end()[-2];
            P b = hull.end()[-1];
            if(a.triangle(b, c) >= 0) hull.pop_back();
            else break;
        }
        hull.push_back(c);
    }
    long long ans = 0;
    for(int i = 0; i < (int)hull.size(); i++) {
        ans += (hull[i].x - (i == 0 ? 1 : hull[i - 1].x)) * (hull[i].y + (i == 0 ? 0 : hull[i - 1].y));
    }
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    while(t--) solve();
}