CF1667B Optimal Partition

给定一个包含 $n$ 个整数的数组 $a$。你需要将 $a$ 划分为若干个连续且非空的子数组（总共有 $2^{n-1}$ 种划分方式）。 设 $s = a_l + a_{l+1} + \ldots + a_r$。对于子数组 $a_l, a_{l+1}, \ldots, a_r$，其价值定义如下： - 如果 $s > 0$，则价值为 $(r-l+1)$； - 如果 $s = 0$，则价值为 $0$； - 如果 $s < 0$，则价值为 $-(r-l+1)$。 请问，采用最优划分方式时，所有子数组价值之和的最大值是多少？

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 5 \cdot 10^5$），表示测试数据组数。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）。 保证所有测试数据中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每组测试数据，输出一个整数，表示采用最优划分方式时所有子数组价值之和的最大值。

测试点 $1$：一种最优划分方式为 $[1, 2]$，$[-3]$。$1+2>0$，因此 $[1, 2]$ 的价值为 $2$。$-3