#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ma 200002
#define buffs 1048576
FILE *f=freopen("heapuri.in","r",stdin);
int v[ma],h[ma],n,i,x,a,lgv,lgh,_i,nod;
char buff[buffs];
int pos=0;
inline void read(int &nr)
{ int semn=1;
    while(buff[pos]<'0'||buff[pos]>'9') if(++pos==buffs) fread(buff,1,buffs,stdin),pos=0;
    nr=0;
    if(buff[pos-1]=='-')semn=-1;
    while(buff[pos]>='0'&&buff[pos]<='9')
    {
        nr=nr*10+buff[pos]-'0';
        if(++pos==buffs)fread(buff,1,buffs,stdin),pos=0;
    }
}
inline void sift(int x)
{
    int ok,cx;
  cx=x;
    do
    {
        ok=0;
        if(x*2<=lgh) ok=x*2;
        if(x*2+1<=lgh&&h[x*2+1]<h[x*2])ok++;
        if(h[ok]>=h[x])ok=0;
        if(ok)
        {
            swap(h[x],h[ok]);
            swap(v[cx],v[ok]);
            x=ok;
        }
    }
    while(ok);
}
inline void urc(int x)
{   int cx;
cx=x;
    while(h[x/2]>h[x])
    {
        swap(h[x/2],h[x]);
       swap(v[x/2],v[cx]);
        x/=2;
    }
}
int main()
{
    freopen ("heapuri.out","w",stdout);
    fread(buff,1,buffs,stdin);
    read(n);
    lgv=lgh=0;
    for(i=1; i<=n; i++)
    {
        read(a);
        if(a!=3)read(x);
        if(a==1)
        {
            v[++lgv]=lgh+1;
            h[++lgh]=x;
            urc(lgh);


        }
        else if(a==3) printf("%d \n",h[1]);
        else
        {
            _i=v[x];
            h[_i]=h[lgh];
            lgh--;
            if(_i>1&&h[_i]<h[_i/2])urc(_i);
            else sift(_i);
        }
    }
}