#include <bits/stdc++.h>
using namespace std;
long long mil() { return numeric_limits<long long>::min(); }
long long mal() { return numeric_limits<long long>::max(); }
long long recur(long long l, long long r, long long i,
                vector<pair<long long, long long>> &ai,
                map<tuple<long long, long long, long long>, long long> &cache) {
  if (i == ai.size()) {
    return 0;
  }
  if (cache.count(make_tuple(l, r, i)) > 0) {
    return cache[make_tuple(l, r, i)];
  }
  auto &e = ai[i];
  cache[make_tuple(l, r, i)] =
      max(abs(e.second - l) * e.first + recur(l + 1, r, i + 1, ai, cache),
          abs(e.second - r) * e.first + recur(l, r - 1, i + 1, ai, cache));
  return cache[make_tuple(l, r, i)];
}
void solve() {
  int N;
  cin >> N;
  vector<pair<long long, long long>> ai(N);
  long long val = 0;
  for (long long i = 0; i < (N); ++i) cin >> val, ai[i] = make_pair(val, i);
  sort(ai.begin(), ai.end(), greater<pair<long long, long long>>());
  map<tuple<long long, long long, long long>, long long> cache;
  long long sum = recur(0, ai.size() - 1, 0, ai, cache);
  cout << sum << endl;
}
int main(int argc, char **argv) {
  long long ti;
  cin >> ti;
  for (long long i = 0; i < (ti); ++i) solve();
}
