#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heapuri.in");
ofstream g("heapuri.out");
int i,n,v[200001],k,a,x;
struct meme{
    int v,p;
}h[200001];
void down_heap(int poz,int n){
    while(poz*2<=n){
        int st=poz*2;
        if(st+1<=n&&v[h[st+1].v]<v[h[st].v])
            st=st+1;
        if(v[h[poz].v]>v[h[st].v]){
            swap(h[poz].v,h[st].v);
            h[h[poz].v].p=poz;
            h[h[st].v].p=st;
            poz=st;
        }
        else
            return;
    }
}
void up_heap(int poz){
    while(poz/2>=1){
        int st=poz/2;
        if(v[h[poz].v]<v[h[st].v]){
            swap(h[poz].v,h[st].v);
            h[h[poz].v].p=poz;
            h[h[st].v].p=st;
            poz=st;
        }
        else
            return;
    }
}
void sort_heap(){
    for(int i=n/2;i>=1;i--)
        down_heap(i,k);
}
int main()
{   f>>n;
    for(i=1;i<=n;i++){
        f>>a;
        if(a==3)
            g<<v[h[1].p]<<'\n';
        else
        if(a==1){
            f>>x;
            h[++k].v=h[k].p=k;
            v[k]=x;
            up_heap(k);
        }
        else{
            f>>x;
            swap(h[k].v,h[h[x].p].v);
            k--;
            down_heap(1,k);
        }
    }
    return 0;
}