Se cunoaste, pentru urmatoarele N zile, pretul unui caiet. In fiecare zi se poate cumpara un caiet (daca nu se detine niciunul) sau vinde caietul detinut, oricat de des, dar niciodata nu se pot detine 2 caiete simultan. Determinati suma maxima de bani ce poate fi castigata, stiind ca in prima zi nu se detine niciun caiet.
- Date de intrare
- Pe prima linie se citeste N. Pe a doua linie se citesc N numere, preturile din fiecare zi.
- Date de iesire
- Se afiseaza un singur numar intreg: profitul maxim posibil.
- Restrictii
- 1 <= N <= 10^5, 1 <= pret <= 10^6
Exemple
Exemplul 1
Intrare
10 15 31 5 15 20 5 17 23 10 18
Iesire
57
Exemplul 2
Intrare
1 50
Iesire
0