Вы разрабатываете рейтинговую систему для онлайн-игры. Каждый раз, когда игрок участвует в матче в этой игре, его рейтинг меняется в зависимости от результатов.
Изначально рейтинг игрока равен \(0\). Он будет участвовать в \(n\) матчах; после \(i\)-го матча рейтинг изменяется на \(a_i\) (рейтинг увеличивается на \(a_i\), если \(a_i\) положительное, или уменьшается на \(|a_i|\), если отрицательное. В последовательности \(a\) нет нулей).
В системе есть дополнительное правило: для заданного целого числа \(k\), если рейтинг игрока достиг значения \(k\), он никогда не опустится ниже него. Формально, если рейтинг игрока хотя бы \(k\), а изменение рейтинга должно сделать его меньше \(k\), то рейтинг снизится ровно до \(k\).
Ваша задача состоит в том, чтобы определить значение \(k\) таким образом, чтобы рейтинг игрока после всех \(n\) матчей был максимально возможным (среди всех возможных целочисленных значений \(k\)). Если существует несколько возможных ответов, выведите любой из них.
Выходные данные
Для каждого набора входных данных выведите одно целое число \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|