Problem F
Overdraft

Banks often charge overdraft fees if you attempt to withdraw more money from your account than is available in your current balance. Given a sequence of deposits and withdrawals (and assuming each deposit and withdrawal is immediately reflected in your balance), determine the minimum (non-negative) starting balance you need to ensure that you will not be charged any overdraft fees over the course of the sequence.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 1,000), which is the number of transactions.

Each of the next n lines contains a single integer t (-10⁶ ≤ t ≤ 10⁶, t ≠ 0). These are the transactions, in the order that they occur. A positive number represents a deposit, a negative number represents a withdrawal. No two transactions occur simultaneously.

Output

Output a single non-negative integer, which is the minimum non-negative balance you must start with in your account in order to avoid any overdraft fees.

3
3
-5
3

2