The workshops for FIT1008 have gotten so popular that outcomes of the workshops have started to appear on prediction markets, where users can bet on the outcome of ordinary events.

As with many famous people, Ali has noticed that he both has control over the outcome of the event and can bet on the result. Time to make a quick buck!

There is one large prediction that is constantly being bet on: "Will Ali bring chocolates into the final workshop?". Here's the thing, though - by bringing / not bringing chocolates into earlier workshops, Ali has been able to impact the market's expectation of what will happen for the final workshop. He knows, for every workshop, what the market odds will be that he will bring the chocolates into the final workshop.

At the start of every workshop, the current market value of the bet is ~b_i~ - this means Ali can purchase 1 "bet" that he will bring chocolates in for ~b_i~ dollars. At this moment, Ali can do one of three actions:

• Pay ~b_i~ dollars, and make a bet that he will bring in chocolates.
• (If he has an open bet) sell one of his existing bets to someone else for ~b_i~ dollars.
• Do nothing.

Because Ali doesn't want to be caught insider trading, he doesn't actually want to own any bets after the final workshop completes. Ali will instead make his money through arbitrage. So the strategy should obviously be to buy a bet in periods where he knows that the market value is set to increase, and then sell his bets at the peak.

The market value of the bet per workshop is fixed - Ali has already decided whether or not he is bringing in the chocolates each day. What we can help Ali with is deciding which of the three actions he should take at the beginning of every workshop.

In order to pass the tests, your solution should have a time complexity of ~O(n\ \log(n))~.

Input

Input will begin with a single integer ~n~ (~1 \leq n \leq 10^5~), the number of workshops.

The next line will contain ~n~ integers ~b_1, b_2, \ldots, b_n~ (~1 \leq b_i \leq 10^9~), ~b_i~ is the market value of the bet for the ~i^{\text{th}}~ workshop.

Output

Output a single integer - the maximum amount of dollars that Ali can make throughout all ~n~ workshops.

Example 1

Input

9
10 5 4 7 9 12 6 2 10

Output

20

Ali can make 2 bets, on the 2nd and 3rd workshop, which costs him $9. He then sells these on the 5th and 6th workshops, netting him ~21 in return (net positive of $12 so far). He then purchases another bet at the 8th workshop and sells at the final workshop ($8 profit), for a total of $20 profit.

Example 2

Input

20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4

Output

41