29869번 - Jada kustutamine 다국어

Me kõik tunneme funktsioone $\min$ ja $\max$, mis leiavad vastavalt vähima ja suurima hulka kuuluva väärtuse. Vaatleme nüüd funktsiooni $\text{mex}$, mis arvu\-hulgale rakendatuna tagastab minimaalse hulka mittekuuluva mittenegatiivse täisarvu (funktsiooni nimi tulebki ingliskeelsest väljendist minimal excluded). Näiteks $\text{mex}(\{1,2,3\}) = 0$ ja $\text{mex}(\{0,1,2,4,5\}) = 3$.

Magnus tutvus funktsiooni $\text{mex}$ definitsiooniga ja leiutas kohe sellel põhineva mängu. Selles mängus saab mängija $N$-elemendilise mittenegatiivsete täisarvude jada $A$ ja koostab selle põhjal jada $B$, korrates järgmisi samme, kuni jadas $A$ on veel elemente:

1. Vali positiivne täisarv $k$, mis ei ületa jada $A$ pikkust.
2. Lisa jada $B$ lõppu jada $A$ esimese $k$ elemendi $\text{mex}$.
3. Kustuta jadast $A$ selle esimesed $k$ elementi.

Mängija ülesanne on valida igal sammul selline $k$ väärtus, et saadud jada $B$ oleks kõigi võimalike hulgas leksikograafiliselt maksimaalne. Tuletame meelde, et jada $x = x_1, x_2, \ldots, x_n$ on jadast $y = y_1, y_2, \ldots, y_m$ leksikograafiliselt suurem, kui

• leidub selline $i$, et $i \le n$ ja $i \le m$ ning $x_1 = y_1$, $x_2 = y_2$, $\ldots$, $x_{i-1} = y_{i-1}$ ja $x_i > y_i$ või
• $n > m$ ja $x_1 = y_1$, $x_2 = y_2$, $\ldots$, $x_m = y_m$.

Sisendi esimesel real on jada $A$ pikkus $N$ ($1 \le N \le 500\,000$) ja teisel real $N$ tühikutega eraldatud täisarvu: jada $A$ elemendid $A_i$ ($0 \le A_i \le N$).

Väljundi esimesele reale väljastada leitud jada $B$ pikkus $M$ ja teisele reale tühikutega eraldatult jada $B$ elemendid $B_1, B_2, \ldots, B_M$.