Вы нашли очень интересный муравейник. Вы настолько им заинтересовались, что решили выяснить, сколько муравьёв в нём находилось в начальный момент (когда вы нашли его).
Для этого вы в течение дня проводили наблюдения и записали массив ai — сколько муравьёв вошло или вышло в i-й момент времени:
Используя свои наблюдения, определите минимальное количество муравьёв, которое могло находиться внутри муравейника до начала наблюдений.
Обратите внимание, что в муравейнике ни в какой момент времени не могло находиться отрицательное количество муравьёв.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество совершённых наблюдений.
Во второй строке содержится n целых чисел a1, a2, ..., an ( - 106 ≤ ai ≤ 106, i = 1, 2, ..., n) — результат i-го наблюдения.
В единственной строке выведите целое число — минимально возможное количество муравьёв внутри муравейника до начала наблюдений.
3
20 -50 30
30
Первый тестовый пример
Количество муравьёв внутри муравейника в процессе наблюдений менялось следующим образом:
