Máme vrece čísel, ktoré je na začiatku prázdne. Postupne s vrecom robíme nasledovné: buď do neho nejaké číslo vložíme, alebo z neho vyberieme najväčšie číslo. Po každej operácii chceme vedieť, aké najväčšie číslo sa vo vreci nachádza (ak nie je vrece prázdne).
Zadanie tejto úlohy ste už asi videli. Tento krát sú ale vstupy väčšie a teda budete musieť naprogramovať efektívnejšie riešenie.
Prvý riadok obsahuje počet operácii $n$. Platí $1 \leq n \leq 2 \cdot 1000$.
Nasleduje $n$ riadkov, $i$-ty z nich popisuje $i$-tu operáciu a má tvar
t x. Ak t je 0, tak z vreca vyberáme najväčšie číslo a x
ignorujeme. Ak t je 1, tak do vreca vkladáme číslo x. Platí $|x| \leq 10^9$.
Je zaručené, že z vreca vyberáme iba ak nie je prázdne.
Na $i$-ty riadok vypíšte jedno celé číslo: najväčšie číslo nachádzajúce
sa vo vreci po $i$-tej operácii. Ak je po $i$-tej operácii vrece prádzne,
vypíšte namiesto toho empty.
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
empty
4
empty