**Time limit:**1.00 s**Memory limit:**512 MB

You will buy and sell a single share

*exactly two times*during the period. More precisely, you will do as follows:

- You buy a share on day $a$ and sell it on day $b$ where $a \le b$.

- You buy a share on day $c$ and sell it on day $d$ where $b \le c \le d$.

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