Izolator

Firma Izomax produkuje wielowarstwowe izolatory cieplne. Każda z i warstw, i=1, 2, ..., n, cechuje się dodatnim współczynnikiem izolacji ai. Warstwy są ponumerowane zgodnie z kierunkiem ucieczki ciepła.

ciepło      ->      || a1 | a2 | ... | ai | ai+1 | ... | an ||      ->     

Współczynnik izolacji całego izolatora, A, określony jest sumą współczynników izolacji jego warstw. Ponadto współczynnik A rośnie, jeśli po warstwie o niższym współczynniku izolacji występuje warstwa o wyższym współczynniku, zgodnie z wzorem: 

A = a_1 + a_2 + ... + a_n + max(0, a_2 - a_1) + max(0, a_3 - a_2) + ... + max(0, a_n - a_{n-1})

Na przykład, współczynnik izolacji izolatora o postaci:

->     || 5 | 4 | 1 | 7 ||      ->

wynosi A = (5+4+1+7)+(7-1) = 23.

Zadanie

Napisz program, który dla zadanych współczynników izolacji warstw a1, a2, ..., an wyznacza taką kolejność warstw, dla której współczynnik izolacji A całego izolatora jest największy.

Wejście

W pierwszym wierszu wejścia zapisana jest liczba warstw n, 1 <= n <= 100000. W kolejnych n wierszach zapisane są współczynniki a1, a2, ..., an, po jednym w każdym wierszu. Współczynniki te są liczbami całkowitymi i spełniają nierówności 1 <= ai <= 10000.

Wyjście

W pierwszym i jedynym wierszu wyjścia Twój program powinien zapisać jedną liczbę całkowitą równą największej możliwej wartości współczynnika izolacji A izolatora zbudowanego z warstw o podanych współczynnikach, ułożonych w odpowiedniej kolejności.

Przykład

Dla wejścia: 

4
5
4
1
7
poprawną odpowiedzią jest: 
24