您正在开发在线游戏的评级系统。每次玩家参加比赛时,该玩家的评分都会根据结果而变化。
最初,玩家的等级为$$$0$$$。有 $$$n$$$ 匹配项;在第 $$$i$$$ 场比赛之后,评分变化等于 $$$a_i$$$(如果 $$$a_i$$$ 为正,则评分增加 $$$a_i$$$;如果为负,则评分减少 $$$|a_i|$$$。序列 $$$a$$$ 中没有零)。
系统有一个附加规则:对于固定整数$$$k$$$,如果玩家的等级达到了值$$$k$$$,则永远不会低于该值。正式来说,如果玩家的评级至少为 $$$k$$$,并且评级更改会使其低于 $$$k$$$,则评级将恰好降低到 $$$k$$$。
你的任务是确定 $$$k$$$ 值,使得所有 $$$n$$$ 比赛后玩家的评分是可能的最大值(在 $$$k$$$ 的所有整数值中)。如果有多个可能的答案,您可以打印其中任何一个。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 匹配数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$; $$$a_i \ne 0$$$) — 第 $$$i$$$ 场比赛后的评分变化。
所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 $$$m$$$ ($$$-10^{18} \le m \le 10^{18}$$$) — $$$k$$$ 的值,这样玩家的评分将是使用该值时可能的最大值。可以证明,至少一个最优答案满足约束$$$-10^{18} \le m \le 10^{18}$$$。
示例
输入 #1
4 4 3 -2 1 2 3 -1 -2 -1 2 4 2 7 5 1 -3 2 -1 -2 2
输出 #1
3 0 25 6
注意
在第一个示例中,如果 $$$k=3$$$,则评级更改如下:$$$0 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow 6$$$。
在第二个示例中,如果 $$$k=0$$$,则评级更改如下:$$$0 \rightarrow 0 \rightarrow 0 \rightarrow 0$$$。
在第三个示例中,如果 $$$k=25$$$,则评级更改如下:$$$0 \rightarrow 4 \rightarrow 6$$$。
在第四个示例中,如果 $$$k=6$$$,则评级更改如下:$$$0 \rightarrow 5 \rightarrow 6 \rightarrow 6 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 8$$$。