Hide

Problem P
Stalínröðun

Languages en is
/problems/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