Rishika is hosting a special kind of auction tonight. Each item's price has an upper limit of price instead of a lower limit. Each item is numbered from 1 to n. The upper limit for the i-th item is pi (1<=i<=n). 
Now there is another special rule for the auction. The purchase price of an item cannot be lower than the items to its left and right simultaenously,i.e. for i-th item, there musn't be two integers j and k such that j<i<k and aj>ai<ak, where ai is the purchase price of i-th item.

Now to gain as much profit as possible, Rishika wants the total price as large as posible without violating the two conditions.

INPUT:
The First line contains a single integer n (1≤n≤500000), the number of items for auction.
The Second line contains the integers p1,p2,…,pn (1≤pi≤10^9),the upper limit on the item price.

OUTPUT:
Print the sum of all the purchase prices.

CONSTRAINTS:
1 ≤ pi ≤ 10^9
30 MARKS:
1 ≤ n ≤ 1000
70 MARKS:
1 ≤ n ≤ 500000