L'alpinista fatxenda P78622

Un alpinista farà un viatge a un sistema muntanyós amb $n$ pics. Cada dia estarà al costat d’un pic d’alçada $a_i$, i haurà de decidir si escalar-lo o no. Però, com que és un fatxenda, després d’escalar un pic d’una certa alçada no en voldrà escalar cap d’alçada més petita. Quina és la màxima suma d’alçades que podrà escalar?

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$, seguida de les $n$ alçades en ordre de visita, totes entre 1 i $10^9$. Suposeu $1 \le n \le 10^5$.

Sortida

Per a cada cas, escriviu la màxima suma d’alçades possible.

Observació

Podeu obtenir 30 punts resolent casos on $n \le 100$, i uns altres 30 punts resolent casos on $a_i \le 100$.