| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 15 | 5 | 5 | 71.429% |
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.
4 1 2 2 3
0
6 4 2 5 1 3 6
5
7 5 5 6 7 1 2 3
1
Pojašnjenje prvog probnog primjera: nije potrebno rezati niz.
Pojašnjenje drugog probnog primjera: 5567 | 123 → 123 | 5567