D. Рейтинговая система
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы разрабатываете рейтинговую систему для онлайн-игры. Каждый раз, когда игрок участвует в матче в этой игре, его рейтинг меняется в зависимости от результатов.

Изначально рейтинг игрока равен $$$0$$$. Он будет участвовать в $$$n$$$ матчах; после $$$i$$$-го матча рейтинг изменяется на $$$a_i$$$ (рейтинг увеличивается на $$$a_i$$$, если $$$a_i$$$ положительное, или уменьшается на $$$|a_i|$$$, если отрицательное. В последовательности $$$a$$$ нет нулей).

В системе есть дополнительное правило: для заданного целого числа $$$k$$$, если рейтинг игрока достиг значения $$$k$$$, он никогда не опустится ниже него. Формально, если рейтинг игрока хотя бы $$$k$$$, а изменение рейтинга должно сделать его меньше $$$k$$$, то рейтинг снизится ровно до $$$k$$$.

Ваша задача состоит в том, чтобы определить значение $$$k$$$ таким образом, чтобы рейтинг игрока после всех $$$n$$$ матчей был максимально возможным (среди всех возможных целочисленных значений $$$k$$$). Если существует несколько возможных ответов, выведите любой из них.

Входные данные

Первая строка содержит одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число $$$m$$$ ($$$-10^{18} \le m \le 10^{18}$$$) — такое значение $$$k$$$, при котором рейтинг игрока будет максимально возможным. Можно показать, что существует хотя бы одно такое значение, которое удовлетворяет ограничениям $$$-10^{18} \le m \le 10^{18}$$$.

Пример
Входные данные
4
4
3 -2 1 2
3
-1 -2 -1
2
4 2
7
5 1 -3 2 -1 -2 2
Выходные данные
3
0
25
6
Примечание

В первом примере, если $$$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$$$.