Problem Statement

Given is $a number sequence A_1, A_2, A_3, \dots, A_N,$ which may contain negative elements.
On a number line, there is a robot at coordinate 0. It will do the following actions in order:

• Move A_1 in the positive direction.
• Move A_1 in the positive direction, and then move A_2 in the positive direction.
• Move A_1 in the positive direction, then move A_2 in the positive direction, and then move A_3 in the positive direction.

$\hspace{140pt} \vdots$

• Move A_1 in the positive direction, then move A_2 in the positive direction, then move A_3 in the positive direction, $\ldots, \dots$, and then move A_N in the positive direction.

Find the greatest coordinate occupied by the robot from the beginning to the end of the process.

Input

Input is given from Standard Input in the following format:
N
$A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N$

Output

Print the greatest coordinate occupied by the robot from the beginning to the end of the process.

Constraints

• $1 \le N \le 200000$
• -$10^8 \le A_i \le 10^8$
• All values in input are integers.

Sample Input 1

3
2 -1 -2

Sample Output 1

5

The robot moves as follows:

• Move 2 in the positive direction, to coordinate 2.
• Move 2 in the positive direction, to coordinate 4. Then move -1 in the positive direction, to coordinate 3.
• Move 2 in the positive direction, to coordinate 5. Then move -1 in the positive direction, to coordinate 4. Then move -2 in the positive direction, to coordinate 2.

The greatest coordinate occupied during the process is 5, so we should print 5.

Sample Input 2

5
-2 1 3 -1 -1

Sample Output 2

2

Sample Input 3

5
-1000 -1000 -1000 -1000 -1000

Sample Output 3

0

In this case, the initial coordinate 0 is the greatest coordinate occupied.

见题面 Input 部分

见题面 Output 部分