Rezolvare PBinfo #398

Cerinţa

De-a lungul principalei străzi din orașul nostru există n plopi, pentru fiecare cunoscându-se înălțimea. Primarul orașului dorește ca plopii să aibă înălțimile în ordine descrescătoare. Pentru aceasta, este posibilă tăierea dintr-un plop a unei bucăți – este o tehnică ecologică, nevătămătoare, în urma căreia plopul nu are de suferit. Plopii nu pot fi înălțați în niciun fel.

Determinați numărul minim de plopi din care se va tăia și lungimea totală minimă a bucăților tăiate.

Date de intrare

Fișierul de intrare plopi2.in conține pe prima linie numărul de plopi n. Urmează n numere naturale nenule, separate prin spaţii, care pot fi dispuse pe mai multe linii, reprezentând înălțimile plopilor.

Date de ieşire

Fișierul de ieșire plopi2.out va conține pe prima linie numerele C T, separate prin exact un spațiu, reprezentând numărul minim de plopi din care se va tăia și lungimea totală minimă a bucăților tăiate.

Restricţii şi precizări

• 2 ≤ n ≤ 100
• înălțimile plopilor vor fi mai mici decât 10000

Exemplu:

plopi2.in

8
5 7 3 6 4 4 2 6

plopi2.out

5 11

Explicație

Vom tăia din plopii numerotați cu 2 4 5 6 8, astfel încât înălțimile să devină 5 5 3 3 3 3 2 2. Lungimea totală a bucăților tăiate este: 2 + 3 + 1 + 1 +4 = 11