Max Rise

Interview

Time limit1sMemory limit512 MB

Summary

Given daily stock prices, find the maximum profit from one buy followed by one later sell, where selling on the same day gives zero.

Level: Easy3 of 10
Topics: Array, Greedy
Solved: No attempts yet

Problem

Someone who can foresee the future knows exactly how the stock price of ANA Company will change over the next $N$ days. Based on this prediction, Jeonggyun wants to buy one share at a suitable time and sell it at a suitable time to earn the greatest possible profit.

Let the stock prices of ANA Company over the next $N$ days be $a_1, a_2, ..., a_N$ . If Jeonggyun buys on day $i$ and sells on day $j$ , he earns $a_j - a_i$ . Since he has plenty of funds, he can buy no matter how high the price is, and if the situation does not work out, he can sell right after buying.

Given the prices of ANA Company over the next $N$ days, what is the maximum profit Jeonggyun can earn by buying one share at a suitable time and selling it at a suitable time?

Input

The first line contains an integer $N$ ( $1 \le N \le 200000$ ).

The second line contains integers $a_1, a_2, ..., a_N$ . Each $a_i$ ( $1 \le a_i \le 10^9$ ) is the stock price of ANA Company on day $i$ .

Output

Print the maximum profit Jeonggyun can earn by buying one share at a suitable time and selling it at a suitable time.

Examples3

Example 1
Input
```
5
4 2 3 1 5
```
Expected output
```
4
```
Example 2
Input
```
3
3 2 1
```
Expected output
```
0
```
Example 3
Input
```
4
7 1 2 6
```
Expected output
```
5
```