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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LC ch[k][0] 
#define RC ch[k][1]
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = n - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)

typedef long long LL;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

const int N = 500010;
const int M = 610000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = (LL)1e18;
const double eps = 1e-9;
inline int dcmp(double x) {
    return (x > eps) - (x < -eps);
}

struct Point {
    LL x, y;
    Point (LL x = 0 , LL y = 0) : x(x) , y(y) {}
    void input() {
        cin >> x >> y; 
    }
    bool operator < (const Point& R) const {
        if (x - R.x == 0)
            return (y - R.y) < 0;
        return (x - R.x) < 0;
    }
    bool operator == (const Point& R) const {
        return (x - R.x) == 0 && (y - R.y) == 0;
    }
    Point operator + (const Point& R) const {
        return Point(x + R.x, y + R.y);
    }
    Point operator - (const Point& R) const {
        return Point(x - R.x, y - R.y);
    }
    Point operator * (const LL& R) const {
        return Point(x * R, y * R);
    }
    /*
    Point operator / (const double& R) const {
        return Point(x / R, y / R);
    }
    */
    LL operator ^ (const Point& R) const {
        return x * R.y - y * R.x;
    }
    LL operator % (const Point& R) const {
        return x * R.x + y * R.y;
    }
    LL slen() {
        return *this % *this;
	}
    /*
    double len() {
        return sqrt(*this % *this);
	}
    double angle() {
        return atan2(y, x);
    } */
}p[N], h[N];

int tp, n;
int stk[N], used[N];

void convex(){
	tp = 0;
	//std::sort(p + 1, p + 1 + n); 
	stk[++tp] = 1;
	for (int i = 2; i <= n; ++i) {
	  while (tp >= 2 
	        && ((p[stk[tp]] - p[stk[tp - 1]]) ^ (p[i] - p[stk[tp]])) >= 0)
	    used[stk[tp--]] = 0;
	  used[i] = 1;  
	  stk[++tp] = i;
	}
	for (int i = 1; i <= tp; ++i) 
	  h[i] = p[stk[i]];
}

void solve() {
	cin >> n; 
	repn(i, 1, n) {
		cin >> p[i].y;
		p[i].x = i;
		used[i] = 0;
	}
	convex();
	LL ans = 0;
	repn(i, 2, tp) {
		ans += (h[i].x - h[i - 1].x) * (h[i].y + h[i - 1].y);
	}
	cout << ans << "\n";
}

int main()
{
	IO;
	int T;
	cin >> T;
	repn(i, 1, T) solve();
	return 0;
}