B. Ant Hill
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have found a very interesting ant hill. You are so intrigued by it that you decided to find out how many ants were inside at the initial moment (when you discovered it).

To do this, you observed throughout the day and recorded an array ai — how many ants entered or exited at the i-th moment in time:

  • |ai| represents the number of ants;
  • The sign of the number indicates the direction (minus — exited, plus — entered)
.

Using your observations, determine the minimum number of ants that could have been inside the ant hill before the observations began.

Note that at no point in time could there be a negative number of ants inside the ant hill.

Input

The first line contains an integer n (1 ≤ n ≤ 105) — the number of observations made.

The second line contains n integers a1, a2, ..., an ( - 106 ≤ ai ≤ 106,  i = 1, 2, ..., n) — the result of the i-th observation.

Output

In a single line, output an integer — the minimum possible number of ants inside the ant hill before the observations began.

Example
Input
3
20 -50 30
Output
30
Note

First test example

The number of ants inside the ant hill changed as follows during the observations:

  • At the beginning, there were 30;
  • 20 entered — a total of 50 became present;
  • 50 exited — there were no ants left;
  • 30 entered — there were 30 ants inside.