#include<iostream>
#include<fstream>
using namespace std;

// v[ i ]= elementul intrat al i-lea in multime (deci, practic sirul pe care il citesc)
// H[ i ]= pozitia in sirul v a elementului de pe pozitia i din heap
// poz[ i ]= pozitia in heap a elementului de pe poztia i in sirul v
// v[H[ i ]]= valoarea elementului de pe pozitia i in heap

int N;
int v[200001], cntV=1;
int H[200001], cntH=1;
int poz[200001], cntPoz=1;

void percolate(int n)
{
    while((n/2 >=1) && (v[H[n]] < v[H[n/2]]))
    {
        int aux = H[n];
        H[n] = H[n/2];
        H[n/2] = aux;

        poz[H[n]] = n;
        poz[H[n/2]] = n/2;        

        n/=2;
    }
}

void list()
{
    for(int i=0;i<cntV;i++)
        cout<<v[i]<<" ";
    cout<<endl;

    for(int i=0;i<cntH;i++)
        cout<<H[i]<<" ";
    cout<<endl;

    for(int i=0;i<cntPoz;i++)
        cout<<poz[i]<<" ";
    cout<<endl;

    cout<<endl;
}

void sift(int n)
{
#ifdef DEBUG
    cout<<"sift()"<<endl;
    cout<<"n="<<n<<endl;
#endif
    int max, aux=0;
    if( (2*n < cntH) && v[H[2*n]]<v[H[n]])
        aux = 2*n;

    if( (2*n +1 < cntH) && v[H[2*n+1]]<v[H[n]])
        if(v[H[2*n+1]] < v[H[2*n]])
            aux = 2*n+1;
    
    while(aux!=0)
    {
#ifdef DEBUG
        cout<<"Schimb "<<n<<" cu "<<aux<<endl;
#endif
        int change = H[n];
        H[n] = H[aux];
        H[aux] = change;

        poz[H[n]] = n;
        poz[H[aux]] = aux;

        n = aux;
        aux = 0;

        if( (2*n < cntH) && v[H[2*n]]<v[H[n]])
            aux = 2*n;

        if( (2*n +1 < cntH) && v[H[2*n+1]]<v[H[n]])
            if(v[H[2*n+1]] < v[H[2*n]])
                 aux = 2*n+1;
    }
#ifdef DEBUG
    cout<<"~sift()"<<endl;
#endif
}

int main()
{
    int bvc;
    fstream fin;
    fin.open("heapuri.in");

    ofstream fout;
    fout.open("heapuri.out");

    fin>>N;
    for(int i=0;i<N;i++)
    {
        int A,B;
        fin>>A;

        if(A==1)
        {
#ifdef DEBUG
            cout<<"Inainte de adaugare "<<endl;
            list();
#endif
            fin>>B;
            v[cntV++] = B;
#ifdef DEBUG
            cout<<"Adaug pe poz "<<cntH<<endl;
#endif
            H[cntH++] = cntV-1;
            poz[cntPoz++] = cntH-1;

            percolate(cntH-1);
#ifdef DEBUG
            list();
            cin>>bvc;
#endif
        } else if(A==2)
        {
            fin>>B;
#ifdef DEBUG
            cout<<"Sterg "<<B;
#endif
            H[poz[B]] = H[cntH-1];
            poz[H[cntH-1]] = poz[B];            
            cntH--;

            if((poz[B]/2 >=1) && (v[H[poz[B]/2]]>v[H[poz[B]]]))
            {                
#ifdef DEBUG
                cout<<"Percolate "<<endl;
#endif
                percolate(poz[B]);
            }
            else            
            {
#ifdef DEBUG
            cout<<"Ininte de sift"<<endl;
            list();
              cout<<"sift"<<endl;
#endif  
              
                sift(poz[B]);
            }
            poz[B] = 0;
#ifdef DEBUG
            list();
            cin>>bvc;
#endif       
        } else if(A==3)
        {
            fout<<v[H[1]]<<endl;
        }        
    }
    fin.close();
    fout.close();
    return 0;
}