#include <fstream>
using namespace std;

ifstream fin("heapuri.in");
ofstream fout("heapuri.out");

int v[200010],cron[200010],i,j,cnt,poz[200010],c,x,n,m;

int main(){
    fin>>m;
    for(;m;m--){
        fin>>c;

        if(c==1){
            fin>>x;
            v[++n]=x;
            cron[++cnt]=x;
            poz[x]=n;

            i=n;
            while(v[i]<v[i/2] && i/2){
                swap(v[i],v[i/2]);
                swap(poz[v[i]],poz[v[i/2]]);
                i/=2;
            }
        }

        if(c==2){
            fin>>x;
            swap(v[poz[cron[x]]],v[n]);
            i=poz[cron[x]];
            swap(poz[cron[x]],poz[v[poz[cron[x]]]]);
            n--;

            while(i*2<=n){
                if(v[i]>v[2*i] || (v[i]>v[2*i+1] && 2*i+1<=n)){

                    if(2*i+1<=n && v[i]>v[2*i+1]){
                        swap(poz[v[i]],poz[v[2*i+1]]);
                        swap(v[i],v[2*i+1]);
                    }else{
                        swap(poz[v[i]],poz[v[2*i]]);
                        swap(v[i],v[2*i]);
                    }

                }else{
                    break;
                }
            }
        }

        if(c==3)
            fout<<v[1]<<"\n";
    }

    return 0;
}