Vasilică are la grădiniţă N
turnuri cu înălţimile h
1
, h
2
, …, 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 ≤ N ≤ 100 000
1 ≤
Înălţimile turnurilor≤ 100 000
- Dacă după aranjarea turnurilor
h
i
≤ h
i+1
atunci turnurilei
şii+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ălțimea 7
.