CF1845D Rating System

你正在为一个网络游戏开发一个评分系统。每当玩家参加一场比赛时，玩家的评分会根据比赛结果发生变化。 最初，玩家的评分为 $0$。共有 $n$ 场比赛；第 $i$ 场比赛后，评分变化为 $a_i$（如果 $a_i$ 为正，则评分增加 $a_i$，如果 $a_i$ 为负，则评分减少 $|a_i|$。序列 $a$ 中没有零）。 该系统有一条额外规则：对于一个固定的整数 $k$，如果玩家的评分达到了 $k$，则之后评分永远不会低于 $k$。具体来说，如果玩家的评分已经至少为 $k$，而某次评分变化会使其低于 $k$，那么评分只会降到 $k$。 你的任务是确定 $k$ 的取值，使得玩家在所有 $n$ 场比赛后最终的评分最大（在所有整数 $k$ 中）。如果有多个可能的答案，你可以输出其中任意一个。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^5$），表示比赛场数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$，$a_i \ne 0$），表示每场比赛后的评分变化。 所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$。

对于每个测试用例，输出一个整数 $m$（$-10^{18} \le m \le 10^{18}$），表示使得玩家最终评分最大的 $k$ 值。可以证明，至少存在一个最优答案满足 $-10^{18} \le m \le 10^{18}$。

在第一个样例中，如果 $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$。 由 ChatGPT 4.1 翻译