Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Buy Low, Sell High

Buy Low, Sell High

Time limit:1.00 s
Memory limit:512 MB

You know the stock price of a company during the next $n$ days.

You will buy and sell a single share exactly two times during the period. More precisely, you will do as follows:
  1. You buy a share on day $a$ and sell it on day $b$ where $a \le b$.
  2. You buy a share on day $c$ and sell it on day $d$ where $b \le c \le d$.
How much money will you earn if you act optimally?

Input

The first input line has an integer $n$: the number of days.

The second line has $n$ integers $p_1,p_2,\dots,p_n$: the stock prices.

Output

Print one integer: the maximum profit.

Constraints
Example 1

Input:
8
4 2 3 5 1 4 2 7


Output:
9

Explanation: First you buy a share on day 2 and sell it on day 4. Then you buy a share on day 5 and sell it on day 8.

Example 2

Input:
2
1 2


Output:
1

Explanation: First you buy a share on day 1 and sell it on day 2. Then you buy a share on day 2 and sell it on day 2.