Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Miškovi na [email protected]
Táto úloha je o dátovej štruktúre - Halda. Ak nevieš čo Halda je, môžeš si o nej viac prečítať v študíjnom texte o Halde.
V Krtkove^[niečo ako Kocúrkovo] majú teraz nový problém. Je viac ľudí, ktorí sa chcú dať zaočkovať ako vakcín. Rozhodli sa preto, že spravia čakáreň, do ktorej sa môžu ľudia zapísať a počkať, kým pre nich bude k dispozícii vakcína. Ostáva už len jeden problém a to koho zavolať na očkovanie ako prvého. Keďže všetci v Krtkove sú zaneprázdnení, potrebujú niekoho kto im naprogramuje čakáreň.
Vašou úlohou bude simulovať čakáreň. Čakáreň pozostáva z dvoch typov akcií. Buď sa niekto s celočíselnou prioritou^[Áno, každý v Krtkove má nejakú prioritu na očkovanie] $p$ prihlási do čakárne alebo máme novú vakcínu, teda človek s najväčšou prioritou bude zaočkovaný a odíde z čakárne. Po každej akcii nás zaujíma, aká je najväčšia priorita medzi ľuďmi v čakárni. Na začiatku je čakáreň prázdna.
Na prvom riadku sa nachádza číslo $n$ - počet akcií ktoré treba spracovať. Nasleduje $n$ riadkov, $i$-ty z nich popisuje $i$-tu akciu a má tvar $t\ x$. Ak $t$ je $0$, tak prišla nová vakcína a $x$ ignorujeme. Ak $t$ je $1$, tak sa do čakárne prihlásil nový človek s prioritou $x$. V prvej akcii sme ponechali na vstupe $x$ kvôli ľahšiemu načítavaniu vstupu (pre obe akcie treba načítať dve čísla).
Je zaručené, že ak prišla nová vakcína v čakárni je aspoň jeden človek. Vo všetkých sadách platí, že $1 \leq n \leq 2 \cdot 10^5$ a $1 \leq x \leq 10^9$.
Vypíšte $n$ riadkov, v $i$-tom jedno celé číslo - najväčšia priorita spomedzi ľudí v čakárni po $i$ akciách. Ak je po $i$-tej akcii čakáreň prázdna, vypíšte namiesto toho prazdna.
10
1 1
1 1
0 0
1 6
0 0
1 2
0 0
0 0
1 4
0 0
1
1
1
6
1
2
1
prazdna
4
prazdna