Start

2019-03-23 11:00 CET

Beta 2019

End

2019-03-23 17:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -266 days 8:13:21

Time elapsed

6:00:00

Time remaining

0:00:00

Problem P
Stalínröðun

/problems/iceland.stalinrodun/file/statement/is/img-0001.png
Sýnidæmi 2
Eitt af þeim fjölmörgu skiptum sem Unnar var að skruna og skoða nýjar færslur á samfélagsmiðlinum LasÞað sá hann færslu á /l/forritunarhúmor um Stalínröðun. Þar var lýst línulegu reikniriti til þess að raða lista en það virkaði með því að fjarlæga öll stök í listanum sem voru ekki í vaxandi röð.

Nú fór Unnar að pæla ,,Hvað með að í staðinn fyrir að eyða út öllum stökum sem eru ekki í vaxandi röð að þá eyðum við út öllum þeim stökum sem eru í vaxandi röð?”. Mjög eðlileg spurning til að spyrja er þá hvað tæki það margar ítranir þangað til við endum með tóman lista?

Stak $a_ i$ er í vaxandi röð ef að fyrir öll $j < i$ gildir að $a_ i \geq a_ j$.

Inntak

Fyrsta línan inniheldur eina heiltölu $1 \leq n \leq 5 \cdot 10^5$. Næsta lína inniheldur $n$ heiltölur $1 \leq a_ i \leq 10^6$.

Úttak

Skrifið út fjölda ítrana til þess að enda með tóman lista.

Sýnidæmi

[ 1 7 5 8 6 3 2 4 ]
Eftir fyrstu ítrun:
[ 5 6 3 2 4 ]
Eftir aðra ítrun:
[ 3 2 4 ]
Eftir þriðju ítrun:
[ 2 ]
Eftir fjórðu ítrun:
[ ]
Svarið er því fjórir.

Stigagjöf

Hópur

Stig

Takmarkanir

1

20

$n \leq 50$, öll $a_ i$ mismunandi

2

30

$n \leq 2\, 500$, öll $a_ i$ mismunandi

3

50

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
3
2 1 3
2
Sample Input 2 Sample Output 2
8
1 7 5 8 6 3 2 4
4