// Abhay Singh Bhadoria ( _Asb_ ) //
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int a[N], dp[N][N];
int main() {
    ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--) {
        int n;
        cin >> n;
        for(int i = 1; i <= n; ++i) cin >> a[i];
        for(int i = 0; i <= n; ++i) {
            for(int j = 1; i + j <= n; ++j) {
                int k = j + i;
                dp[j][k] = max(dp[j + 1][k] + (n - i) * a[j], dp[j][k - 1] + (n - i) * a[k]);
            }
        }
        cout << dp[1][n] << endl;
    }
}

Ly8gQWJoYXkgU2luZ2ggQmhhZG9yaWEgKCBfQXNiXyApIC8vCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBOID0gMmUzICsgNTsKaW50IGFbTl0sIGRwW05dW05dOwppbnQgbWFpbigpIHsKICAgIGlvc19iYXNlIDo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgY2luLnRpZShOVUxMKTsgY291dC50aWUoTlVMTCk7CiAgICBpbnQgdGM7CiAgICBjaW4gPj4gdGM7CiAgICB3aGlsZSh0Yy0tKSB7CiAgICAgICAgaW50IG47CiAgICAgICAgY2luID4+IG47CiAgICAgICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyArK2kpIGNpbiA+PiBhW2ldOwogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPD0gbjsgKytpKSB7CiAgICAgICAgICAgIGZvcihpbnQgaiA9IDE7IGkgKyBqIDw9IG47ICsraikgewogICAgICAgICAgICAgICAgaW50IGsgPSBqICsgaTsKICAgICAgICAgICAgICAgIGRwW2pdW2tdID0gbWF4KGRwW2ogKyAxXVtrXSArIChuIC0gaSkgKiBhW2pdLCBkcFtqXVtrIC0gMV0gKyAobiAtIGkpICogYVtrXSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgY291dCA8PCBkcFsxXVtuXSA8PCBlbmRsOwogICAgfQp9

MQo1CjEgMiAzIDQgNQ==

1
5
1 2 3 4 5