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

#include <bits/stdc++.h>
using namespace std;

ifstream cin("heap.in");
ofstream cout("heap.out");

int n, H[100001];

void push_up(int k){
    while(k > 1){
        if(H[k] <= H[k / 2])
            return ;
        else
            swap(H[k], H[k / 2]), k /= 2;
    }
}

void push_down(int k, int n){
    while(2 * k <= n){
        int p = 2 * k;
        if(p + 1 <= n && H[p + 1] > H[p])
            p++;
        if(H[k] >= H[p])
            return ;
        else
            swap(H[p], H[k]), k = p;
    }
}

int cnt = 0;

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int c, x;
        cin >> c;
        if(c == 1)
            cin >> x, H[++cnt] = x, push_up(cnt);
        else
            cout << H[1] << '\n', H[1] = H[cnt], cnt--, push_down(1, cnt);
    }
    return 0;
}