#include<cstdio>
#include<algorithm>
using namespace std;
int n,o,ind,i,x,q,w,cnt,poz[200001];
struct hip
{
    int val;
    int ord;
} h[200001];
void up(int i)
{
    if(i!= 1 && h[i].val<h[i/2].val)
    {
        swap(h[i],h[i/2]);
        up(i/2);
    }
}
void down(int i)
{
    int fiu=0; //indicele fiului
    if(2*i<=ind)
    {
        fiu=2*i;
        if(fiu+1 <= ind && h[fiu+1].val <  h[fiu].val)fiu=2*i+1;
        if(h[fiu].val > h[i].val)fiu=0;
    }
    if(fiu)
    {
        swap(h[fiu],h[i]);
        down(fiu);
    }
}
int main()
{
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        scanf("%d",&o);
        if(o == 1)
        {
            scanf("%d",&x);
            ind++;
            cnt++;
            h[ind].val = x;
            h[ind].ord = cnt;
            poz[cnt]=ind;
            up(ind);
        }
        if(o == 2)
        {
            scanf("%d",&x);
            swap(h[poz[x]],h[ind]);
            ind --;
            up(w);
            down(w);
        }
        if(o == 3)printf("%d\n",h[1].val);
    }

}