//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];
        for (int i = 1; i <= n; ++i) {
            mx = max(mx, (n - i) * a[i] + dp[i]);
            int cnt = 0;
            for (int j = i + 1; j <= n; ++j) {
                int cur = dp[i] + (j - i) * (a[i] + a[j]);
                if (++cnt >= 500 && i > 10) break;
                if (cur > dp[j]) {
                    dp[j] = cur;
                } else {
                    break;
                }
            }
        }
        cout << mx << "\n";
    }
}