deal

Vasilică are la grădiniță $N$ turnuri cu înălțimile $h_1, h_2, \dots, h_N$. Când așază în linie niște turnuri, cel puțin două, astfel încât înălțimile lor să fie în ordine crescătoare, Vasilică spune că a construit un deal. Înălțimea dealului este egală cu înălțimea celui mai înalt turn folosit. Iată, de exemplu, că așezând în ordine turnurile cu înălțimile $2 \ 4 \ 4 \ 7 \ 9$ a format un deal cu înălțimea $9$.

Vasilică și-ar dori să așeze în linie cele $N$ turnuri, formând o succesiune de dealuri astfel încât suma înălțimilor dealurilor formate să fie maximă.

Cerință

Scrieți un program care, cunoscând înălțimile celor $N$ turnuri, va determina suma înălțimilor dealurilor ce se pot forma așezând în linie cele $N$ turnuri, maximă posibil.

Date de intrare

Fișierul de intrare deal.in conține pe prima linie numărul natural $N$. Pe cea de a doua linie se află $N$ numere naturale separate prin spații, reprezentând înălțimile celor $N$ turnuri.

Date de ieșire

Fișierul de ieșire deal.out va conține o singură linie pe care va fi scris un număr natural reprezentând cerința problemei.

Restricții și precizări

• $2 \leq N \leq 100 \ 000$;
• $1 \leq$ Înălțimile turnurilor $\leq 100 \ 000$;
• Dacă după aranjarea turnurilor $h_i \leq h_{i+1}$ atunci turnurile $i$ și $i + 1$ fac parte din același deal.

Exemplu

deal.in

7
10 2 2 2 7 5 2

deal.out

22

Explicație

O soluție posibilă cu suma înălțimilor $22$ ar fi: $2 \ 10 \ 2 \ 5 \ 2 \ 2 \ 7$. S-au format trei dealuri: $2 \ 10$ (cu înălțimea $10$) și $2 \ 5$ (cu înălțimea $5$) și $2 \ 2 \ 7$ cu înățimea $7$.