CSES - HIIT Open 2018 - 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

• 1 \le n \le 5 \cdot 10^5
• 1 \le p_i \le 10^9

# 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.