#include "bits/stdc++.h"
 
using namespace std;
 
#define sz(s)   int32_t(s.size())
#define all(x)  begin(x), end(x)
 
using ll = long long;
using ld = long double;

const int N = 5e5 + 5;

int p[N];

struct Point {
    int x, y;
    Point (int _x, int _y) : x(_x), y(_y) {}
    Point () : x(0), y(0) {}
};

void operator -= (Point& a, Point b) {
    a.x -= b.x, a.y -= b.y;
}

int cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

int orientation(Point o, Point a, Point b) {
    a -= o, b -= o;
    int det = cross(a, b);
    if (det < 0)    return -1;
    else return +1;
}

void solve() {
    int n;  cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    p[0] = p[n + 1] = 0;
    vector<Point> pts;
    for (int i = 1; i <= n; i++) {
        Point P(i, p[i]);
        while (sz(pts) >= 2 && orientation(pts[sz(pts) - 2], pts[sz(pts) - 1], P) != -1) {
            pts.pop_back();
        }
        pts.push_back(P);
    }
    int res = 0;
    for (int i = 0; i + 1 < sz(pts); i++) {
        Point a = pts[i], b = pts[i + 1];
        res += (a.y + b.y) * (b.x - a.x);
    }
    cout << res << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tests = 1;  cin >> tests;
    for (int test_case = 1; test_case <= tests; test_case++) {
        solve();
    }
}