Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Tornit

Tornit


View task | Model solution | Statistics


Tornit

Time limit:1.00 s
Memory limit:128 MB

Sinulle annetaan $n$ kuutiota, joista sinun tulee rakentaa torneja. Vaatimuksena on, että aina kun tornissa on päällekkäin kaksi kuutiota niin ylempi on alempaa pienempi.

Sinun täytyy käsitellä kuutiot siinä järjestyksessä kuin saat ne. Voit joko laittaa kuution vanhan tornin huipulle tai aloittaa uuden tornin. Mikä on pienin mahdollinen määrä torneja?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: kuutioiden määrä.

Seuraavalla rivillä on $n$ kokonaislukua $k_1,k_2,\ldots,k_n$: kunkin kuution koko siinä järjestyksessä kuin saat ne.

Tuloste

Tulosta yksi kokonaisluku: pienin mahdollinen tornien määrä.

Rajat
Esimerkki

Syöte:
5
3 8 2 1 5


Tuloste:
2