#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

inline int read() {
  rint x=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
  return x*f;
}

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

const int N = 2e6 + 10;

struct SegTree {
  std::vector<int> a;
  SegTree(int n) : a((n + 1) * 4, 0) { this->build(1, 1, n); }
#define lson ((o) << 1)
#define rson ((o) << 1 | 1)
  void build(int o, int l, int r) {
    if (l == r) return void(a[o] = -1e18);
    int mid = (l + r) / 2;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    a[o] = std::max(a[lson], a[rson]);
  }
  int query(int o, int l, int r, int L, int R) {
    if (l >= L && r <= R) return a[o];
    int mid = (l + r) / 2;
    int res = -1e18;
    if (L <= mid) res = std::max(res, query(lson, l, mid, L, R));
    if (R > mid) res = std::max(res, query(rson, mid + 1, r, L, R));
    return res;
  }
  void change(int o, int l, int r, int x, int val) {
    if (l == r) return void(a[o] = std::max(a[o], val));
    int mid = (l + r) / 2;
    if (x <= mid)
      change(lson, l, mid, x, val);
    else
      change(rson, mid + 1, r, x, val);
    a[o] = std::max(a[lson], a[rson]);
  }
#undef lson
#undef rson
};

int dp[N];

void solution() {
  int n;
  n = read();
  std::vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i) a[i] = read();
  std::vector<int> s(n + 1);
  for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
  // 离散化前缀和数组 s
  std::vector<int> vs(s.begin(), s.end());
  std::sort(vs.begin(), vs.end());
  std::map<int, int> belong;
  int tot = 0;
  for (auto i : vs)
    if (!belong.count(i)) belong[i] = ++tot;
  // s2 是离散化后的 s
  std::vector<int> s2(n + 1);
  for (int i = 1; i <= n; ++i) s2[i] = belong[s[i]], std::cout << s2[i] << ' ';
  auto chmax = [](auto& x, auto y) { x = std::max(x, y); };
  std::vector<SegTree> seg(3, SegTree(tot));
  // 下面这行相当于暴力代码的 dp[0] = 0
  for (int i = 0; i < 3; ++i) seg[i].change(1, 1, tot, belong[0], 0);
  for (int i = 1; i <= n; i++) {
    // 对应上述第一个转移方程
    if (s2[i] > 1) chmax(dp[i], seg[2].query(1, 1, tot, 1, s2[i] - 1) + i);
    // 第二个转移方程
    chmax(dp[i], seg[1].query(1, 1, tot, s2[i], s2[i]));
    // 第三个转移方程
    if (s2[i] < tot) chmax(dp[i], seg[0].query(1, 1, tot, s2[i] + 1, tot) - i);
    // 单点修改
    seg[0].change(1, 1, tot, s2[i], dp[i] + i);
    seg[1].change(1, 1, tot, s2[i], dp[i]);
    seg[2].change(1, 1, tot, s2[i], dp[i] - i);
  }
  print(dp[n]);
}

signed main() {
  int T = read();
  while(T--) {
    solution();
  }
  return 0;
}

样例都过不了