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

Маг планирует посетить $$$n$$$ магических источников в заданном порядке. Известно, что при посещении $$$i$$$-го источника его мана изменится на $$$a_i$$$ (это число может быть и положительным, и отрицательным, и нулем). Если количество маны мага становится отрицательным, маг погибает. Какое минимальное количество маны необходимо магу в начале своего путешествия, чтобы он смог успешно посетить все $$$n$$$ источников и остаться живым?

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

В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 500000$$$) — количество магических источников.

Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — изменение количества маны при посещении $$$i$$$-го источника.

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

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

Пример
Входные данные
6
3 -4 2 -3 -2 7
Выходные данные
4