STOCKS2

Miltos is in the fortunate position to have reliable information about the price of a stock in the stock market and wants to exploit it! Specifically, he knows the price change of a stock for each of the next N days. For example, if the change for a certain day is -3 (or, correspondingly, 4), this means that the stock price decreased by 3 euros (or, correspondingly, increased by 4 euros) compared to the price of the previous day.

Miltos can choose the day to buy the stock, but he must compulsorily sell it after the end of the N-th day. Additionally, Miltos is not at all risky and wants from the moment he buys the stock, its price to remain higher than the price at which he bought it.

Write a program that will help Miltos calculate the maximum profit he can achieve if he buys the stock at the best possible time.

Input

The first line of input will contain the number N of days. The second line of input will contain N integers ~a_i~ corresponding to the change in the price of the stock on the ~i~-th day. The numbers will be separated in pairs by spaces.

Output

The output should consist of a single line containing exactly one integer: the maximum profit Miltos can achieve.

Constraints

2 ~\le~ N ~\le~ 1.000.000

-1.000 ~\le~ a~_i~ ~\le~ 1.000

Execution time limit: 1 sec.
Memory limit: 16 MB.

Examples of Input - Output

1st

STDIN (metoxes.in)

8
-1 3 -4 5 -1 4 0 -2

STDOUT (metoxes.out)

6

Explanation: Miltos can buy the stock on the 3rd day (at the end). Let's say the stock price at that moment is x. Then on the 4th day it will be x + 5, on the 5th it will be x + 5 - 1 = x + 4, and so on. On the last day, the stock price will be x + 5 - 1 + 4 + 0 - 2 = x + 6, so if he sells it then, he will have a profit of (x + 6) - x = 6. Additionally, from the 4th day onwards, the stock price is always higher than x. If Miltos chose to buy the stock on any other day, he wouldn't manage to have a profit greater than 6.

2nd

STDIN (metoxes.in)

10
5 -6 7 -8 14 12 -11 9 -5 4

STDOUT (metoxes.out)

23

Explanation: Miltos can buy the stock on the 4th day (let's say at price x). On the following days, the stock price will be respectively: x + 14, x + 26, x + 15, x + 24, x + 19, x + 23, which is always at least x. Thus, Miltos achieves the maximum profit of 23 when he sells it on the last day.

3d

STDIN (metoxes.in)

5
1 2 1 2 -10

STDOUT (metoxes.out)

0

Explanation: Regardless of which day Miltos buys, on the last day, the stock will have a significant drop, and he will definitely incur a loss. Therefore, it's in his best interest not to buy at all and have a profit of 0.