#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

// #define int long long
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define BOOST ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
struct P {
    int x, y;
    P() : P(0, 0) {}
    P(int x, int y) : x(x), y(y) {}
    P operator-(P &other) {
        return {this->x - other.x, this->y - other.y};
    }
};
ll cross(P p0, P p1, P p2) {
    return 1LL * (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}
int orientation(P p0, P p1, P p2) {
    ll c = cross(p0, p1, p2);
    if(c > 0) return 1; // counterclockwise
    if(c < 0) return -1; // clockwise
    return 0;
}
vector<P> convex_hull(vector<P> ps) {
    int n = ps.size();
    P p0 = *min_element(all(ps), [&](P &p1, P &p2) {
        if(p1.x == p2.x) {
            return p1.y < p2.y;
        } else return p1.x < p2.x;
    });
    sort(all(ps), [&](P &p1, P &p2) {
        int o = orientation(p0, p1, p2);
        if(o == 0) {
            ll dx1 = p1.x - p0.x, dx2 = p2.x - p0.x, dy1 = p1.y - p0.y, dy2 = p2.y - p0.y;
            return dx1 * dx1 + dy1 * dy1 < dx2 * dx2 + dy2 * dy2;
        }
        return o == -1;
    });

    vector<P> v{ps[0], ps[1]};
    for(int i = 2; i < n; i++) {
        while(orientation(v[v.size() - 2], v.back(), ps[i]) == 1) {
            v.pop_back();
        }
        v.push_back(ps[i]);
    }
    return v;
}
void test_case() {
    int n;
    cin >> n;
    vector<P> ps;
    for(int i = 0; i < n; i++) {
        int val;
        cin >> val;
        ps.emplace_back(i, val);
    }
    ps.emplace_back(n - 1, 0);
    ps.emplace_back(0, 0);
    vector<P> ch = convex_hull(ps);
    ll ans = 0;
    for(int i = 0; i < (int)ch.size(); i++) {
        int j = (i + 1) % (ch.size());
        ans += cross({0,0}, ch[j], ch[i]);
    }
    cout << ans << "\n";
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tc = 1;
    cin >> tc;
    while(tc--) {
        test_case();
    }
    return 0;
}