CF1845D.Rating System

You are developing a rating system for an online game. Every time a player participates in a match, the player's rating changes depending on the results.

Initially, the player's rating is $0$. There are $n$ matches; after the $i$-th match, the rating change is equal to $a_i$ (the rating increases by $a_i$ if $a_i$ is positive, or decreases by $|a_i|$ if it's negative. There are no zeros in the sequence $a$).

The system has an additional rule: for a fixed integer $k$, if a player's rating has reached the value $k$, it will never fall below it. Formally, if a player's rating at least $k$, and a rating change would make it less than $k$, then the rating will decrease to exactly $k$.

Your task is to determine the value $k$ in such a way that the player's rating after all $n$ matches is the maximum possible (among all integer values of $k$). If there are multiple possible answers, you can print any of them.

你正在为一款在线游戏开发一个评分系统。每当玩家参加一场比赛时，其评分将根据比赛结果发生变化。

初始时，玩家的评分为 $0$。共有 $n$ 场比赛；在第 $i$ 场比赛后，评分变化量为 $a_i$（若 $a_i$ 为正，则评分增加 $a_i$；若 $a_i$ 为负，则评分减少 $|a_i|$。序列 $a$ 中不含零）。

该系统还有一条附加规则：对某个固定的整数 $k$，若玩家的评分曾达到过值 $k$，则此后其评分将永远不会低于 $k$。形式化地讲，若玩家当前评分为至少 $k$，而某次评分变化会使评分低于 $k$，则该次变化后评分将恰好变为 $k$。

你的任务是确定整数 $k$ 的取值，使得玩家经过全部 $n$ 场比赛后的最终评分为所有可能的整数 $k$ 中的最大值。若存在多个满足条件的 $k$，输出任意一个即可。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of matches.

The second line contains $n$ integer $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$; $a_i \ne 0$) — the rating change after the $i$-th match.

The sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print one integer $m$ ($-10^{18} \le m \le 10^{18}$) — the value of $k$ such that the rating of the player will be the maximum possible when using this value. It can be shown that at least one of the optimal answers meets the constraint $-10^{18} \le m \le 10^{18}$.

对于每个测试用例，输出一个整数 $m$（$-10^{18} \le m \le 10^{18}$）—— 即使得玩家评分为最大可能值的 $k$ 的取值。可以证明，至少存在一个最优解满足约束 $-10^{18} \le m \le 10^{18}$。

In the first example, if $k=3$, then the rating changes as follows: $0 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow 6$.

In the second example, if $k=0$, then the rating changes as follows: $0 \rightarrow 0 \rightarrow 0 \rightarrow 0$.

In the third example, if $k=25$, then the rating changes as follows: $0 \rightarrow 4 \rightarrow 6$.

In the fourth example, if $k=6$, then the rating changes as follows: $0 \rightarrow 5 \rightarrow 6 \rightarrow 6 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 8$.

在第一个例子中，若 $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$。