Division of the pasture

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka recently bought a large pasture for their stallions.

The pasture can be imagined as a long strip of \(n\) plots. On the \(i\)-th plot (numbered from left to right) of the pasture, grass grows with a nutritive value of \(a_i\). The value of \(a_i\) can be negative — this means that on the \(i\)-th plot, grass grows that does more harm than good.

Zenyk and Marichka realized that they rushed into buying such a large pasture, and now they are scratching their heads about what to do with it.

They decided to divide the pasture with a fence into two parts and keep one part for themselves, while selling the other. The fence will run between two plots of the field. Each of the two parts must contain at least one plot. The first (leftmost) plot will remain with our horse breeders (horse breeders are people who breed horses, what did you think?).

Zenyk and Marichka want to keep the part with the maximum possible total nutritive value of the grass, and sell the one with the minimum possible.

Let \(s_1\) be the sum of the nutritive values of the grass on the plots that Zenyk and Marichka keep, and \(s_2\) be the sum on the plots they sell. What is the maximum possible difference \(s_1 - s_2\) that Zenyk and Marichka can achieve?

Input

The first line contains an integer \(n\) — the number of plots in the pasture.

The second line contains \(n\) integers \(a_i\) — the nutritive value of the grass on the \(i\)-th plot of the pasture.

Output

In a single line, output an integer — the maximum possible value of the difference \(s_1 - s_2\).

Constraints

\(2 \le n \le 2 \cdot 10^5\),

\(|a_i| \le 10^9\).

Scoring consists of the following blocks:

• 1 point for each sample from the statement,

• 16 points: all numbers have the same sign,

• 47 points: \(n \le 200\), \(|a_i| \le 10^6\),

• 33 points: without additional constraints.

You will receive the points for a block only if your program passes all tests in the block.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 -5 3 7 2 -15 10 3	9

Input (stdin) сopy	Output (stdout) сopy
4 0 0 0 0	0

Input (stdin) сopy	Output (stdout) сopy
5 -50 -10 -10 30 -10	-30

Input (stdin) сopy	Output (stdout) сopy
5 1000000000 1000000000 1000000000 47 47	3000000000

Notes

In the first example from the statement, Zenyk and Marichka have six ways to divide the pasture into two parts.

• Keep \([-5]\) and sell \([3, 7, 2, -15, 10, 3]\). In this case, \(s_1 = -5, s_2 = 3+7+2+(-15)+10+3=10, s_1-s_2=-5-10=-15\).

• Keep \([-5, 3]\) and sell \([7, 2, -15, 10, 3]\). Then \(s_1 = -5 + 3 = -2, s_2 = 7+2+(-15)+10+3=7, s_1-s_2=-2-7=-9\).

• Keep \([-5, 3, 7]\) and sell \([2, -15, 10, 3]\). Then \(s_1 = -5 + 3 + 7 = 5, s_2 = 2+(-15)+10+3=0, s_1-s_2=5-0=5\).

• Keep \([-5, 3, 7, 2]\) and sell \([-15, 10, 3]\). Then \(s_1 = -5 + 3 + 7 + 2 = 7, s_2 = (-15)+10+3=-2, s_1-s_2=7-(-2)=9\).

• Keep \([-5, 3, 7, 2, -15]\) and sell \([10, 3]\). Then \(s_1 = -5 + 3 + 7 + 2 + (-15) = -8, s_2 = 10+3=13, s_1-s_2=-8-13=-21\).

• Keep \([-5, 3, 7, 2, -15, 10]\) and sell \([3]\). Then \(s_1 = -5 + 3 + 7 + 2 + (-15) + 10 = 2, s_2 = 3, s_1-s_2=2-3=-1\).

The maximum possible difference is \(9\).

In the second example, regardless of the division of the pasture, the difference is zero.

In the third example, the answer is negative and equals \(-30\).

In the fourth example, the answer does not fit in a 32-bit integer.