Rating System
Contest: Educational Codeforces Round 151 (Rated for Div. 2)
Difficulty rating: 1800
Tags: binary search, brute force, data structures, dp, dsu, greedy, math, two pointers

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
4
4
3 -2 1 2
3
-1 -2 -1
2
4 2
7
5 1 -3 2 -1 -2 2

Example output:
3
0
25
6

Editorial:
Let's fix some $$$k$$$ and look at the first and the last moment when the rating should fall below $$$k$$$, but doesn't. After such moments, the rating is equal to $$$k$$$. So we can "delete" all changes (array elements) between those moments. And the remaining changes (to the left from the first moment and to the right from the last moment) can be considered without any additional constraints (the value of $$$k$$$ doesn't affect those changes).
Using this fact, we can see that the total rating is not greater than the sum of the whole array minus some continuous segment. So the maximum possible final rating doesn't exceed the sum of the array minus the minimum sum segment (this segment can be empty, if all elements are positive). In fact, there is always such $$$k$$$ that provides such rating. Let the minimum sum segment be $$$[l; r]$$$, then $$$k$$$ is equal to the prefix sum from $$$1$$$-st to $$$(l-1)$$$-th positions of the array.
The only remaining question is: why the rating after $$$r$$$-th match is equal to $$$k$$$? It can't fall below $$$k$$$ (since the rating is at least $$$k$$$ already); and if it is greater than $$$k$$$, then there is a positive suffix of the segment $$$[l; r]$$$, so we can remove it, and the sum of the segment would decrease. Which means the segment $$$[l; r]$$$ is not minimum sum segment, which contradicts the previous statement. So the rating after $$$r$$$-th match is equal to $$$k$$$.