- Time limit: 1.00 s
- Memory limit: 512 MB
You know the stock price of a company during the next days.
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 and sell it on day where .
- You buy a share on day and sell it on day where .
How much money will you earn if you act optimally?
Input
The first input line has an integer : the number of days.
The second line has integers : 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.