#include <fstream>
#include <iostream>
using namespace std;
ifstream f("heapuri.in");
ofstream g("heapuri.out");
struct vect{
    int val;
    int i;
}v[200005];
int x,t,n,poz[200005];
int MIN(int a,int b){
    return a>b?b:a;
}
void checkup(int k){
    while(k>1&&v[k].val>v[k/2].val){
        swap(v[k],v[k/2]);
        swap(poz[v[k].i],poz[v[k/2].i]);
        k/=2;
    }
}
void checkdown(int k){
    while(k*2<=n){
        int maxi=k*2;
        if(k*2+1<=n&&v[k*2+1].val>v[k*2].val){
            maxi=k*2+1;
        }
        if(v[k].val<v[maxi].val){
            swap(v[k],v[maxi]);
            swap(poz[v[k].i],poz[v[maxi].i]);
            k=maxi;
        }else{
            break;
        }
    }
}
int main(){
    f>>x;
    for(int i=1;i<=x;i++){
        f>>t;
        if(t==1){
            n++;
            f>>v[n].val;
            v[n].i=n;
            poz[n]=n;
            checkup(n);
        }else if(t==2){
            int p;
            f>>p;
            v[poz[p]]=v[n];poz[v[n].i]=poz[p];n--;checkup(poz[p]);checkdown(poz[p]);
        }else{
            if(n%2!=0){
                g<<MIN(v[n].val,v[n-1].val)<<"\n";
            }else{
                g<<v[n].val<<"\n";
            }
        }
    }
    f.close();g.close();return 0;
}