#include "bits/stdc++.h"

using namespace std;

typedef long long int64;

#define x first
#define y second
typedef pair<int,int> pii;
typedef double dbl;
typedef pair<dbl, dbl> pdd;
const dbl eps = 1e-9;

struct pt {
  dbl x, y;
  pt () {}
  pt (const dbl &x, const dbl &y): x(x), y(y) {}
};

pt operator +(const pt &a, const pt &b) {
  return pt(a.x + b.x, a.y + b.y);
}

pt operator -(const pt &a, const pt &b) {
  return pt(a.x - b.x, a.y - b.y);
}

dbl operator %(const pt &a, const pt &b) {
  return a.x * b.y - a.y * b.x;
}

struct line {
  dbl A, B, C;
  line () {}
  line (const dbl &A, const dbl &B, const dbl &C): A(A), B(B), C(C) {}
  pt intersect(const line &l, bool* success = 0) const {
    // Ax + By = -C
    // A'x + B'y = -C'
    dbl det = A * l.B - B * l.A;
    if (fabs(det) < eps) {
      if (success != 0)
        *success = false;
      return pt();
    }
    if (success != 0) *success = true;
    dbl detx = (-C) * l.B - B * (-l.C);
    dbl dety = A * (-l.C) - (-C) * l.A;
    return pt(detx/det, dety/det);
  }
  dbl getY(const dbl& x) {
    return (-C - A * x) / B;
  }
};

int relax(const line& lineA, const line& lineB,
           bool upperA, bool upperB, pdd& infr, bool& active) {
  bool success;
  pt Z = lineA.intersect(lineB, &success);
  int touch = 0;
  if (!success) {
    touch = -1; // we should have a way to go from one parallel line
                  // to another in cleverIntersect
    // lines are parallel
    // is the borderline of j higher than the one of i?
    bool higher = -lineB.C / lineB.B >
          -lineA.C / lineA.B;
    if (fabs(-lineB.C / lineB.B + lineA.C / lineA.B) < eps)
      return touch;
    if (!(((upperA && upperB) || (!upperA && upperB))
     ^ higher)) {
      active = false;
    }
  } else {
    if ((pt(lineA.A,lineA.B) % pt(lineB.A,lineB.B) < 0)
      ^ upperA) {
      if (infr.y > Z.x - eps) {
    touch = 1;
    infr.y = Z.x;
      }
    } else {
      if (infr.x < Z.x + eps) {
    touch = 2;
    infr.x = Z.x;
      }
    }
  }
  if (infr.x > infr.y) active = false;
  return touch;
}

int IT = 0;

void naiveIntersect(const vector<line> &hplanes,
            const vector<bool> &upper,
                          vector<pdd>& influence,
                 // x-segment [l,r] determining the segment
                 // where the corresponding line occurs
                 // in the border of the intersection
              vector<bool>& active) {
  int n = hplanes.size();
  assert(hplanes.size() == upper.size());
  influence.resize(n);
  active.resize(n, true);
  for (int i = 0; i < n; ++i) {
    // i intersect the i'th line with each of the remaining lines
    // and find the segment of influence
    pdd infr = make_pair(-1e9, 1e9);
    for (int j = 0; j < n && active[i]; ++j) {
      ++IT;
      if (i == j) continue;
      bool tactive = true;
      relax(hplanes[i], hplanes[j], upper[i], upper[j],
            infr, tactive);
      active[i] = tactive;
    }
    influence[i] = infr;
  }
}

void cleverIntersect(const vector<line> &hplanes,
             const vector<bool> &upper,
                          vector<pdd>& influence,
                 // x-segment [l,r] determining the segment
                 // where the corresponding line occurs
                 // in the border of the intersection
              vector<bool>& active,
             int start) {
  int n = hplanes.size();
  assert(hplanes.size() == upper.size());
  influence.resize(n);
  active.resize(n, true);
  vector<bool> used(n, false);
  vector<int> q(n);
  q[0] = start;
  int ql = 0;
  int qr = 1;
  used[start] = true;
  for (; ql < qr; ++ql) {
    int i = q[ql];
    used[i] = true;
    pdd infr = make_pair(-1e9,1e9);
    int go[2] = {-1,-1};
    for (int j = 0; j < n && active[i]; ++j) {
      ++IT;
      if (i == j) continue;
      bool tactive = true;
      int touch = relax(hplanes[i], hplanes[j], upper[i], upper[j],
            infr, tactive);
      if (touch == -1 && !used[j]) {q[qr++] = j; used[j] = true;}
      if (touch > 0) go[touch-1] = j;
      active[i] = tactive;
    }
    for (int j = 0; j < 2; ++j)
      if (go[j] >= 0 && !used[go[j]]){ q[qr++] = go[j]; used[go[j]] = true;}
    influence[i] = infr;
  }
}


const int maxn = (int)1.1e5;
const int logn = 17;
int a[maxn];
int64 S[maxn];
int64 dp[maxn];
pair<int, int64> MS[logn][maxn];
int PART = 120;
void solve() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];
  S[0] = a[0];
  for (int i = 1; i < n; ++i) S[i] = S[i-1] + int64(a[i]);

  // TODO: initialize mergesort log

  for (int i = 0; i < n; ++i) dp[i] = S[i] * int64(i+1);
 // for (int i = 0; i < n; ++i) cerr << "dp[" << i << "] = " << dp[i] << endl;
  for (int i = 0; i * PART < n; ++i) {
    int R = min((i+1) * PART, n);
    int L = i * PART;
   // cerr << L << ".." << R << endl;
    for (int j = L; j < R; ++j) {
      for (int k = L; k < j; ++k) {
        //cout << j << " -> " << k << endl;
        dp[j] = max(dp[j], dp[k] + (S[j] - S[k]) * int64(j - k));
      }
    }
    if (R == n) break;
    vector<line> lines;
    vector<pdd> influence;
    vector<pii> ids;
    vector<bool> used(R-L, false);
    IT = 0;
    for (int j0 = L; j0 < R; ++j0) {
     // cerr << "j0=" << j0 << endl;
      if (used[j0-L]) continue;
      vector<int> q(R-L);
      vector<int> start(R-L);
      q[0] = j0;
      start[0] = -1;
      int ql = 0, qr = 1;
      for (; ql < qr; ++ql) {
    int j = q[ql];
    used[j-L] = true;
    vector<line> loc_lines;
    vector<bool> loc_upper;
    vector<pii> loc_ids;
    int my_start = -1;
    for (int k = L; k < R; ++k)
      if (j != k) {
        if (k == start[ql]) my_start = loc_lines.size();
        loc_lines.push_back(line(S[k]-S[j], k-j, dp[j]-dp[k]
            + int64(j)*S[j] - int64(k)*S[k]));
        loc_upper.push_back(k > j);
        loc_ids.push_back(make_pair(j,k));
      }
    vector<pdd> loc_influence;
    vector<bool> active;
    if (start[ql] == -1)
      naiveIntersect(loc_lines, loc_upper, loc_influence, active);
    else
      cleverIntersect(loc_lines, loc_upper, loc_influence,
                      active, my_start);
    for (int k = 0; k < (int)loc_lines.size(); ++k)
      if (active[k]) {
       // cout << j << " ==> " << lines.size() << "(" << loc_upper[k] << ")" << endl;
        lines.push_back(loc_lines[k]);
        influence.push_back(loc_influence[k]);
        ids.push_back(loc_ids[k]);
        if (!used[ids.back().y-L]) {
          q[qr] = ids.back().y;
          used[ids.back().y-L] = true;
          start[qr] = j;
          qr++;
        }
    }
      }
    }
  // cerr << IT << endl;
   /* for (int j = 0; j < (int)lines.size(); ++j) {
      cout << "j=" << j << endl;
      cout << ids[j].x << " -- " << ids[j].y << endl;
      cout << lines[j].A << "x + " << lines[j].B << "y + " << lines[j].C << " = " << 0 << endl;
      cout << influence[j].x << ".." << influence[j].y << endl;
    }*/
    vector<int> good_points;
    for (int j = 0; j < (int)influence.size(); ++j) {
      good_points.push_back((int)influence[j].x);
      good_points.push_back((int)influence[j].x+1);
      good_points.push_back((int)influence[j].y);
      good_points.push_back((int)influence[j].y+1);
    }
    for (int j = 0; j < (int)good_points.size(); ++j) {
      good_points[j] = max(good_points[j], R-1);
      good_points[j] = min(good_points[j], n-1);
    }
    good_points.push_back(R-1);
    good_points.push_back(n-1);
    sort(good_points.begin(), good_points.end());
    good_points.erase(unique(good_points.begin(), good_points.end()),
                      good_points.end());

    for (int j = 1; j < (int)good_points.size(); ++j) {
      int l = good_points[j-1];
      int r = good_points[j];
      vector<int> borders;
     // cout << "l..r=" << l << ".." << r << endl;
      for (int k = 0; k < (int)lines.size(); ++k) {
        if (influence[k].x < (dbl)l + eps &&
       influence[k].y > (dbl)r - eps)
      borders.push_back(k);
      }

      for (int k = 0; k < (int)borders.size(); ++k) {
    int u[2] = {ids[borders[k]].x, ids[borders[k]].y};
    for (int p = 0; p < 2; ++p)
      if (u[p] < l) {
        dp[l] = max(dp[l], dp[u[p]] + (S[l]-S[u[p]])*int64(l-u[p]));
      //  cout << "dp[" << l << "] = " << dp[l] << "(" << u[p] << ")" << endl;
      }
      }

      vector<pair<int64, int>> sums(r-l+1);
      for (int k = l; k <= r; ++k) sums[k-l] = make_pair(S[k],k);
    //  sort(sums.begin(), sums.end());

      if ((int)borders.size() == 0) continue;
      sort(borders.begin(), borders.end(), [&] (int a, int b) {
    if (fabs(lines[a].getY((dbl)(l+r)/2.) -
           lines[b].getY((dbl)(l+r)/2.)) > eps)
      return lines[a].getY((dbl)(l+r)/2.) <
         lines[b].getY((dbl)(l+r)/2.);
    return lines[a].B < lines[b].B;
      });
     // cout << "l="  << l << " r=" << r << endl;
     // for (int k = 0; k < (int)borders.size(); ++k) cout << borders[k] << ' ';
     // cout << endl;

      for (int k = 0; k < (int)sums.size(); ++k) {
    int lb = 0;
    int rb = borders.size() - 1;
    int res = borders.size()-1;
    while (lb <= rb) {
      int mid = (lb+rb)/2;
      if (lines[borders[mid]].getY(sums[k].y) >= sums[k].x) {
        res = mid;
        rb = mid - 1;
      } else {
        lb = mid + 1;
      }
    }
    int ptr = res;
    //cout << sums[k].y << " ptr=" << ptr << endl;
    int cand[4] = {0,0,0,0};
    if (ptr > 0) cand[0] = ids[borders[ptr-1]].x,
                 cand[1] = ids[borders[ptr-1]].y;
    cand[2] = ids[borders[ptr]].x;
    cand[3] = ids[borders[ptr]].y;
    for (int p = 0; p < 4; ++p) {
      if (sums[k].y <= cand[p]) continue;
      dp[sums[k].y] = max(dp[sums[k].y], dp[cand[p]] +
        int64(sums[k].y - cand[p]) * (S[sums[k].y] - S[cand[p]]));
    //  cout << "dp[" << sums[k].y << "] = " << dp[sums[k].y] << "(" << cand[p] << ")" << endl;
    }
      }
    }
  }
  cerr << (double)clock() / CLOCKS_PER_SEC << endl;
  cout << dp[n-1] << "\n";

}


int main() {
  ios_base::sync_with_stdio(0);
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) solve();
}