#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

using ll = long long;

const int N = 5e5 + 5;
const int T = 1 << 22;
const ll inf = -1e18;
const int C = 1e9 + 7;
using pll = pair<ll, ll>;

struct Node {
    pll Ln;
    int l, r;

    Node() {
        l = r = -1;
        Ln = {0, inf};
    }
};

Node t[T];
int Sz = 0;

int create() {
    t[Sz] = Node();
    return Sz++;
}


ll val(pll Ln, ll x) {
    return Ln.first * x + Ln.second;
}

int add(int v, int l, int r, pll Ln) {
    if (v == -1)
        v = create();
    int mid = (l + r) >> 1;
    bool L = val(Ln, l) < val(t[v].Ln, l);
    bool M = val(Ln, mid) < val(t[v].Ln, mid);
    if (M) swap(t[v].Ln, Ln);
    if (r - l == 1) return v;
    if (L == M) t[v].r = add(t[v].r, mid, r, Ln);
    else t[v].l = add(t[v].l, l, mid, Ln);
    return v;
}

ll get(int v, int l, int r, ll x) {
    if (v == -1) return inf;
    ll cur = val(t[v].Ln, x);
    if (r - l == 1) return cur;
    int mid = (l + r) >> 1;
    if (x < mid) return min(get(t[v].l, l, mid, x), cur);
    return min(get(t[v].r, mid, r, x), cur);
}

ll a[N], dp[N];

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n), c(n);
    for (auto& i : a) cin >> i;
    vector<ll> dp(n + 1, 0);
    auto w = [&](int l, int r) -> ll {
        if (l >= r) return 0;
        return -(1ll * (r - l - 1) * (a[r] + a[l]) + dp[l]);
    };
    deque<pair<ll,ll>> k = {{0, 1}};
    for (int i = 1; i <= n; ++i) {
        dp[i] = w(k[0].first, i);
        if (i == n) {
            break;
        }
        ++k[0].second;
        if (k.size() >= 2 && k[0].second == k[1].second) {
            k.pop_front();
        }
        while (!k.empty() && w(k.back().first, k.back().second) >= w(i, k.back().second)) {
            k.pop_back();
        }
        if (k.empty()) {
            k.push_back({i, i + 1});
        } else if (w(k.back().first, n) >= w(i, n)) {
            int left = k.back().second, right = n;
            while (right - left > 1) {
                int mid = (left + right) >> 1;
                (w(k.back().first, mid) >= w(i, mid)
                 ? right
                 : left) = mid;
            }
            k.push_back({i, right});
        }
    }
    cout << -dp[n] << '\n';
}

int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#else
    freopen("input.txt", "r", stdin);
#endif
    int t;
    cin >> t;
    while (t--)
    solve();
    return 0;
}