310518: CF1845D. Rating System

D. Rating Systemtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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}$.

ExampleInput

4
4
3 -2 1 2
3
-1 -2 -1
2
4 2
7
5 1 -3 2 -1 -2 2

Output

3
0
25
6

Note

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$.

题目大意：
你正在为在线游戏开发一个评分系统。每当玩家参与一场比赛时，玩家的评分会根据比赛结果变化。最初，玩家的评分是0。共有n场比赛；在第i场比赛后，评分变化等于a_i（如果a_i是正数，评分增加a_i，如果是负数，评分减少|a_i|。序列a中没有零）。系统有一个额外的规则：对于固定的整数k，如果玩家的评分达到了k值，它将永远不会低于这个值。正式地说，如果玩家的评分至少是k，并且评分变化会使它低于k，那么评分将恰好降至k。

你的任务是确定k的值，使得n场比赛后玩家的评分尽可能高（在所有整数k值中）。如果存在多个可能的答案，你可以打印其中任何一个。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤3×10^5）——比赛的数量。
- 第二行包含n个整数a_1, a_2, …, a_n（-10^9≤a_i≤10^9；a_i≠0）——第i场比赛后的评分变化。
- 所有测试用例的n之和不超过3×10^5。

输出：
- 对于每个测试用例，打印一个整数m（-10^18≤m≤10^18）——使得使用这个值时玩家的评分尽可能高的k值。可以证明，至少有一个最优解满足约束-10^18≤m≤10^18。题目大意： 你正在为在线游戏开发一个评分系统。每当玩家参与一场比赛时，玩家的评分会根据比赛结果变化。最初，玩家的评分是0。共有n场比赛；在第i场比赛后，评分变化等于a_i（如果a_i是正数，评分增加a_i，如果是负数，评分减少|a_i|。序列a中没有零）。系统有一个额外的规则：对于固定的整数k，如果玩家的评分达到了k值，它将永远不会低于这个值。正式地说，如果玩家的评分至少是k，并且评分变化会使它低于k，那么评分将恰好降至k。 你的任务是确定k的值，使得n场比赛后玩家的评分尽可能高（在所有整数k值中）。如果存在多个可能的答案，你可以打印其中任何一个。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1≤n≤3×10^5）——比赛的数量。 - 第二行包含n个整数a_1, a_2, …, a_n（-10^9≤a_i≤10^9；a_i≠0）——第i场比赛后的评分变化。 - 所有测试用例的n之和不超过3×10^5。 输出： - 对于每个测试用例，打印一个整数m（-10^18≤m≤10^18）——使得使用这个值时玩家的评分尽可能高的k值。可以证明，至少有一个最优解满足约束-10^18≤m≤10^18。