Overdraft

Interview

Time limit1sMemory limit1024 MB

Summary

Given a sequence of deposits and withdrawals, find the smallest non-negative starting balance so the running total never drops below zero.

Level: Easy3 of 10
Topics: Prefix sum, Implementation, Greedy, Array
Solved: No attempts yet

Problem

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 \le n \le 1{,}000$ ), which is the number of transactions.

Each of the next $n$ lines contains a single integer $t$ ( $-10^6 \le t \le 10^6$ , $t \neq 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.

Examples1

Example 1
Input
```
3
3
-5
3
```
Expected output
```
2
```