Problem O
Stalínröðun
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 |
