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

Problem PStalínröðun

Inntak

Úttak

Sýnidæmi

Stigagjöf

Problem P
Stalínröðun