Problem G: Investing Stocks

Problem G: Investing Stocks

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 41  Solved: 19
[Submit][Status][Web Board]

Description

Mr Hu decides to go to invest stocks. He will always focus on one stock. Every day he will either buy or sell stocks (or, doing nothing is also ok). What's more, he can own at most one share of the stock at any time. Notice that he will always buy or sell the stocks at current price.

Since Mr Hu has super power, he can know in advance the price on each day of the following \(n\) days.

Mr Hu initially owns no stocks. He wants to know how many money at most he can earn.


Input

The first line contains an integer \(n(1\leq n\leq 5\times 10^5)\), representing the number of days.

Then \(n\) lines follow, among which the \(i\)-th line contains an integer \(a_i(1\leq a_i\leq 10^6)\), representing the price of the stock on the \(i\)-th day.

Output

Output an integer \(ans\) in one line, representing how mant money at most Mr Hu can earn.

Sample Input

5
1
3
2
6
4

Sample Output

6

HINT

[Submit][Status]