Egzotična Elegancija

Ivan: “Dečki, treba nam još jedan elegantan zadatak za studentsko. Mogli bi isprobati staru tehniku da jedan od nas započne nekim klasičnim početkom pa zatim netko nastavi nekom rečenicom itd.”

Marin: “Može, evo ja ću započeti. Imaš niz od n brojeva. . . ”

Josip: “. . . i treba ga razrezati na dijelove uz najmanji mogući broj rezova. . . ”

Ivan: “. . . tako da je preslagivanjem tih dijelova moguće složiti neopadajući niz! Odličan zadatak, hvala dečki!”

U prvom je retku prirodan broj n (1 ≤ n ≤ 106) iz teksta zadatka.

U drugom je retku niz od n prirodnih brojeva manjih ili jednakih 2 · 109.

Ispišite najmanji mogući broj rezova tako da je moguće dobivene dijelove niza presložiti u neopadajući niz.

Pojašnjenje prvog probnog primjera: nije potrebno rezati niz.

Pojašnjenje drugog probnog primjera: 5567 | 123 → 123 | 5567