Given $n$ integers $a_1, a_2, \dots, a_n$.

You need to select a set of intervals $[l, r]$ such that:

1. No selected interval contains another.
2. For every positive integer $i \le n$, at least one selected interval covers position $i$.

Find the maximum possible sum of the sums of all selected intervals.

Definitions:

• An interval $[l, r]$ contains an interval $[l', r']$ if and only if $l \le l'$ and $r \ge r'$.
• An interval $[l, r]$ covers position $i$ if and only if $l \le i \le r$.
• The sum of an interval $[l, r]$ is equal to $\sum_{i=l}^r a_i$.

Input

The first line contains a positive integer $n$, representing the length of the sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the given sequence.

Output

Output a single integer representing the answer.

Examples

Input 1

3
-1 3 2

Output 1

7

Note

The optimal solution selects intervals $[1, 2]$ and $[2, 3]$, which satisfy the condition of not containing each other and covering all positions from $1$ to $n$. Thus, the answer is $(-1 + 3) + (3 + 2) = 7$.

Input 2

5
3 1 -4 -1 5

Output 2

5

Input 3

6
4 5 2 -3 1 -6

Output 3

11

Constraints

This problem uses bundled testing. The special constraints for each subtask are as follows:

• Subtask 1 (10 points): $n \le 5$;
• Subtask 2 (20 points): $n \le 300$;
• Subtask 3 (20 points): $n \le 5000$;
• Subtask 4 (20 points): $a_i \ge 0$;
• Subtask 5 (30 points): No additional constraints.

For all data, $1 \le n \le 5 \times 10^5$ and $|a_i| \le 10^6$.