Un max-heap este un arbore binar complet cu următoarea proprietate suplimentară: valoarea din orice nod este mai mare sau egală cu valorile din orice nod descendent.

Similar se definește noțiunea de min-heap: valoarea din orice nod este mai mică sau egală cu valorile descendenților.

Într-un max-heap rădăcina are valoare maximă, iar într-un min-heap rădăcina are valoare minimă. Nu se precizează nicio relație între valorile din fiii unui nod.

Următorul arbore binar complet este max-heap:

Pentru ca un arbore binar complet să fie max-heap (și similar pentru min-heap), fiecare nod din arbore trebuie:

• să fie mai mare sau egal cu descendenții săi (dacă există)
• să fie mai mic sau egal cu tatăl său (dacă există)

Să presupunem că un arbore binar complet H[] are proprietatea de max_heap, cu excepția unui nod k. Cum îl corectăm, astfel încât să devină max-heap?! Distingem două cazuri:

• dacă nodul k este mai mare decât tatăl său (H[k] > H[k/2) îl vom muta în sus în arbore, până când acesta devine max-heap. Această operație se numește promovare a unui nod în heap;
• dacă nodul k este mai mic decât cel puțin unul dintre fii săi (H[k] < H[2*k] și/sau H[k] < H[2*k+1]) îl vom muta în jos în mod convenabil, până când arborele devine max_heap. Această operație se numește cernere a unui nod în arbore.

Cerința

Se consideră o colecție de numere naturale, inițial vidă. Asupra ei se fac două tipuri de operații:

• 1 x – valoarea x se adaugă în colecție;
• 2 – cea mai mare valoare din colecție se afișează, apoi se elimină din colecție.

Dându-se un șir de m operații, să se afișeze în ordine rezultatele operațiilor de tip 2.

Date de intrare

Fișierul de intrare heap.in conține pe prima linie numărul m, iar pe următoarele m linii câte o operație.

Date de ieșire

Fișierul de ieșire heap.out va conține rezultatele operațiilor de tip 2, câte unul pe o linie, în ordinea în care au fost efectuate.

Restricții și precizări

• 1 ≤ m ≤ 250.000
• 1 ≤ x ≤ 1.000.000.000

Exemplu:

heap.in

12
1 18
1 12
1 3
2
1 3
1 15
2
2
1 8
2
1 19
2

heap.out

18
15
12
8
19