Egzotična Elegancija
시간 제한3초메모리 제한1024 MB
조각을 재배열해 비감소 수열로 만들 수 있도록 하는 최소 절단 횟수를 구한다.
문제
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