Gazzzua

Interview

Time limit1sMemory limit256 MB

Summary

Given known future prices over N minutes, buy at most one coin per minute and sell any number at any time, maximizing total profit.

Level: Medium6 of 10
Topics: Greedy, Implementation, Math, Array
Solved: No attempts yet

Problem

The year is 2119, and Jeongmyeong has finally developed a time machine. Jihoon, born poor, decides firmly to use the time machine to go back 100 years and change his miserable life through the cryptocurrency Juhong Coin. He has the Juhong Coin price chart handed down through his family since his grandfather's generation, so a wealthy life is as good as secured.

However, since the time machine is not yet perfect, he returns to the present once the time limit expires. Juhong Coin also comes with the following trading restrictions imposed by the exchange.

At most 1 Juhong Coin can be bought per minute.
Any number of Juhong Coins can be sold.
No fees are charged on any transaction.

Of course, he may also do nothing and simply pass the time without buying or selling. Because Jeongmyeong holds the price chart, he already knows exactly how the price will change from now on. Determine the maximum profit Jeongmyeong can earn from trading Juhong Coin after going back to the past.

Input

The first line gives the time machine's time limit $N$ in minutes as an integer. ( $1 \le N \le 10^5$ )

The second line gives the price of Juhong Coin for each minute, $N$ values separated by spaces. The price of Juhong Coin is a positive integer at most 1,000.

Output

On the first line, print the maximum profit Jeongmyeong can earn from trading Juhong Coin.

Examples2

Example 1
Input
```
4
1 2 3 4
```
Expected output
```
6
```
Example 2
Input
```
6
1 5 10 2 4 3
```
Expected output
```
16
```