A famous idol group ACPC (Adelaide Charming Pop Crew) has announced an upcoming concert in Australia, attracting massive attention from fans across the country.

Tickets are sold through an online platform called Ticketex. The platform allows users to monitor ticket prices, which fluctuate daily based on demand. To discourage external reselling, each user is restricted to holding at most one ticket at any time. However, users are allowed to return their ticket before the concert begins and receive a refund.

While exploring the system, you discover a critical flaw in Ticketex's refund mechanism. Instead of refunding the original purchase price, the platform refunds the ticket price on the day of return. Users are allowed to return the ticket and then rebuy it on the same day, just make sure that at most one ticket is held at any time.

Utilising this information, determine the maximum profit you can gain by exploiting this bug before the concert begins. As a hardcore fan, you must make sure to keep one ticket for yourself to attend the concert at the end.

Input

The input consists of:

• One line with one integer ~N~ (~1 \leq N \le 10^4~), number of days before the concert begins.
• One line with ~N~ integers ~p_1, p_2, \dots, p_N~ (~1 \leq p_i \le 10^4~), where ~p_i~ indicates the price of the ticket on day ~i~-th.

Output

Output a single integer indicating the maximum profit you can gain from exploiting the refund bug while keeping one ticket for yourself at the end.

Example

Input 1

7
1 2 7 4 5 6 2

Output 1

6

One optimal strategy is buying ticket on the day ~1~, then asking for refund on day ~3~, gaining a profit of ~7-1=6~. Then you rebuy the ticket on day ~4~, and return it on day ~6~, gaining an extra profit of ~6-4=2~. Finally, you buy your ticket on day ~7~, your profit in total is ~6+2-2=6~.

Input 2

6
1 2 3 4 5 6

Output 2

-1

The best profit you can make is ~-1~ from buying the ticket for you on day ~1~. There's no other way keep a higher profit by exploiting the refund the system while still keeping a ticket for you at the end.

Input 3

6
6 5 4 3 2 1

Output 3

-1

Input 4

1
10

Output 4

-10

The ticket is only sold for one day. So you buy that ticket for yourself.