评分保护线

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

玩家初始评分为 $0$，依次参加 $n$ 场比赛。第 $i$ 场比赛后评分增加 $a_i$，其中 $a_i$ 可能为负，但不为零。

评分系统还选定一个整数 $k$：一旦玩家的评分曾达到至少 $k$，之后评分便不会低于 $k$。也就是说，保护规则生效后，如果一次变化本应使评分低于 $k$，评分只会降到 $k$。

请选择整数 $k$，使全部比赛结束后的评分最大。如果有多个最优的 $k$，输出任意一个。

输入格式

第一行一个整数 $t$，表示测试用例数。

每个测试用例第一行一个整数 $n$；第二行包含 $n$ 个非零整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一行一个整数 $k$。若有多个最优答案，可输出任意一个。

保证至少存在一个满足 $-10^{18}\le k\le10^{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

数据范围

对所有数据：

• $1\le t\le10^4$；
• $1\le n\le3\times10^5$；
• $-10^9\le a_i\le10^9$ 且 $a_i\ne0$；
• 单个输入文件内所有测试用例的 $n$ 之和不超过 $3\times10^5$。

本题采用独立测试点计分，每个测试点等分；通过一个测试点中的全部测试用例才能获得该点分数。

提示

令 $p_i=\sum_{j=1}^i a_j$ 且 $p_0=0$。若保护线在某个前缀峰值处生效，其对最终评分的提升等于该峰值到后续最低前缀和的落差。