您有一个长度为 $$$n$$$ 的数组 $$$a$$$,其中包含 非零 整数。最初,您有 $$$0$$$ 硬币,您将执行以下操作,直到 $$$a$$$ 为空:
- 令 $$$m$$$ 为 $$$a$$$ 的当前大小。选择一个整数$$$i$$$,其中$$$1 \le i \le m$$$,获得$$$|a_i|$$$$$$^{\text{*}}$$$硬币,然后:
- 如果$$$a_i \lt 0$$$,则将$$$a$$$替换为$$$[a_1,a_2,\ldots,a_{i - 1}]$$$(即删除以$$$a_i$$$开头的后缀);
- 否则,将 $$$a$$$ 替换为 $$$[a_{i + 1},a_{i + 2},\ldots,a_m]$$$ (即删除以 $$$a_i$$$ 结尾的前缀)。
找出该过程结束时您可以拥有的最大硬币数量。
$$$^{\text{*}}$$$这里$$$|a_i|$$$表示$$$a_i$$$的绝对值:当$$$a_i \gt 0$$$时等于$$$a_i$$$,当$$$a_i \lt 0$$$时等于$$$-a_i$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$, $$$a_i \ne 0$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出过程结束时您可以拥有的最大硬币数量。
示例
输入复制
363 1 4 -1 -5 -96-10 -3 -17 1 19 2011
输出复制
23 40 1
注意
第一个测试用例中如何获取$$$23$$$硬币的示例如下:
- $$$a = [3, 1, 4, -1, -5, \color{red}{-9}] \xrightarrow{i = 6} a = [3, 1, 4, -1, -5]$$$,并获得 $$$9$$$ 硬币。
- $$$a = [\color{red}{3}, 1, 4, -1, -5] \xrightarrow{i = 1} a = [1, 4, -1, -5]$$$,并获得 $$$3$$$ 硬币。
- $$$a = [\color{red}{1}, 4, -1, -5] \xrightarrow{i = 1} a = [4, -1, -5]$$$,并获得 $$$1$$$ 硬币。
- $$$a = [4, -1, \color{red}{-5}] \xrightarrow{i = 3} a = [4, -1]$$$,并获得 $$$5$$$ 硬币。
- $$$a = [4, \color{red}{-1}] \xrightarrow{i = 2} a = [4]$$$,并获得 $$$1$$$ 硬币。
- $$$a = [\color{red}{4}] \xrightarrow{i = 1} a = []$$$,并获得$$$4$$$硬币。
在第二个测试用例中如何获取$$$40$$$硬币的示例如下:
- $$$a = [-10, -3, -17, \color{red}{1}, 19, 20] \xrightarrow{i = 4} a = [19, 20]$$$,并获得 $$$1$$$ 硬币。
- $$$a = [\color{red}{19}, 20] \xrightarrow{i = 1} a = [20]$$$,并获得 $$$19$$$ 硬币。
- $$$a = [\color{red}{20}] \xrightarrow{i = 1} a = []$$$,并获得$$$20$$$硬币。