A93498.最优分段

给定一个包含 $n$ 个整数的数组 $a$。你需要将 $a$ 划分为若干个连续且非空的子数组。

对任意子数组 $a_l,a_{l+1},\ldots,a_r$，令 $s=a_l+a_{l+1}+\cdots+a_r$，它的价值定义为：

• 如果 $s>0$，价值为 $(r-l+1)$；
• 如果 $s=0$，价值为 $0$；
• 如果 $s<0$，价值为 $-(r-l+1)$。

你可以用任意方式把整个数组切成若干段（每个元素必须属于且只属于一段）。问：所有子数组价值之和的最大值是多少？

第一行一个整数 $t$，表示测试数据组数。

每组测试数据：

• 第一行一个整数 $n$；
• 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

每组测试数据输出一行一个整数，表示最大总价值。

样例解释

例如第一组：可以分成 $[1,2]$ 和 $[-3]$。

• $1+2>0$，价值是 $2$
• $-3<0$，价值是 $-1$
  总价值 $2+(-1)=1$，这是最优答案。