Hide

Problem C
Tornbygge

/problems/tornbygge/file/statement/sv/img-0001.png
Bild motsvarande Sample $1$

Den här veckan har Kim slutat bygga pyramider och övergått till att bygga torn med en serie ordnade bitar. Tornen byggs ett åt gången och en bit åt gången. Den första valda biten blir basen till det första tornet. Därefter, om den valda biten är bredare än toppen på det aktuella tornet säger vi att tornet är färdigbyggt och den valda biten blir basen till ett nytt torn. Om den valda biten inte är bredare placeras den på godtyckligt vis ovanpå det aktuella tornet.

Givet ordningen och bredden på de valda bitarna, hur många torn kommer byggas?

Indata

Ett heltal $N$ ($1 \leq N \leq 10^5$) följt av en rad med $N$ heltal $x_ i$ ($1 \leq x_ i \leq 10^6$) motsvarande bredden på respektive bit i ordningen som de väljs.

Utdata

Ett heltal, antal torn som byggs.

Sample Input 1 Sample Output 1
10
4 3 3 2 1 2 2 1 1 3
3
Sample Input 2 Sample Output 2
5
2 2 2 2 2
1
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Languages English, Svenska
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in