//I wrote this code 4 u today
#include <bits/stdc++.h>

template<class t> using vc = std::vector<t>;

#define nd node*
#define pnd pair<nd, nd>

typedef long long ll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    std::sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(std::unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    std::reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;

using namespace std;

const int K = 1488;

#define int ll

mt19937 rnd(228);

int R = 1;

struct Tree {
    vector<int> t, psh;

    Tree() {
        t.resize(R * 2, -1), psh.resize(R * 2, -1);
    }

    void push(int node) {
        if (psh[node] == -1) {
            return;
        }
        for (int i = node * 2; i <= node * 2 + 1; ++i) {
            t[i] = psh[node], psh[i] = psh[node];
        }
        psh[node] = -1;
    }

    void update(int ql, int qr, int nv, int node = 1, int nl = 1, int nr = R) {
        if (ql <= nl && nr <= qr) {
            psh[node] = nv, t[node] = nv;
            return;
        }
        if (qr < nl || nr < ql) {
            return;
        }
        int nm = (nr + nl) / 2;
        push(node);
        update(ql, qr, nv, node * 2, nl, nm), update(ql, qr, nv, node * 2 + 1, nm + 1, nr);
    }

    int gett(int ind, int node = 1, int nl = 1,int nr = R) {
        if (nl == nr) return t[node];
        int nm = (nr + nl) / 2;
        push(node);
        if (nl <= ind && ind <= nm) {
            return gett(ind, node * 2, nl, nm);
        } else {
            return gett(ind, node * 2 + 1, nm + 1, nr);
        }
    }
};

int32_t main() {
    std::cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    ll t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        R = 1;
        while (R <= n) R <<= 1;
        vector<int> a(n);
        for (auto &i : a) {
            cin >> i;
        }
        vector<int> dp(n + 1, 0);
        a.insert(a.begin(), 0);
        int mx = (n - 1) * a[1];
        Tree tree;
        auto get = [&](int i) -> int {
            int wasi = tree.gett(i);
            if (wasi == -1) return 0;
            assert(i > wasi);
            return dp[wasi] + (i - wasi) * (a[wasi] + a[i]);
        };
        for (int i = 1; i <= n; ++i) {
            dp[i] = get(i);
            mx = max(mx, (n - i) * a[i] + dp[i]);
            int l = i, r = n + 1;
            while (r - l > 1) {
                int mid = (l + r) / 2;
                int cur = dp[i] + (mid - i) * (a[i] + a[mid]);
                dp[mid] = get(mid);
                if (mid == i) {
                    l = mid;
                    continue;
                }
                if (cur >= dp[mid]) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            if (l >= i + 1) {
                tree.update(i + 1, l, i);
            }
            for (int j = i + 1; j <= l; ++j) {
                int cur = dp[i] + (j - i) * (a[i] + a[j]);
                if (cur >= dp[j]) {
                    dp[j] = cur;
                } else {
                    break;
                }
            }
        }
        cout << mx << "\n";
    }
}