3. Aktuálny problém

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¹ 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ň.

Úloha

Vašou úlohou bude simulovať čakáreň. Čakáreň pozostáva z dvoch typov akcií. Buď sa niekto s celočíselnou prioritou² \(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.

Formát vstupu

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\).

Formát výstupu

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.

Príklad

Input:

10
1 1
1 1
0 0
1 6
0 0
1 2
0 0
0 0
1 4
0 0

Output:

1
1
1
6
1
2
1
prazdna
4
prazdna