#include <fstream>

using namespace std;


ifstream f("heapuri.in");
ofstream g("heapuri.out");

int st[1000001],v[200001],poz[10000001],index,x,n,t,q;
void actualizare(int r)
{
    while(r/2)
    {
        if(st[r] < st[r/2])
        {
            poz[st[r]]=r/2;
            poz[st[r/2]]=r;
            int a=st[r/2];
            st[r/2]=st[r];
            st[r]=a;
        }
        else
            break;
        r=r/2;
    }
}
void actualizare_1(int r)
{
    if(2*r+1<=index)
    {
        if((st[2*r] < st[r]) && st[2*r] <= st[2*r+1])
        {
            poz[st[2*r]]=r;
            poz[st[r]]=2*r;
            int a=st[2*r];
            st[2*r]=st[r];
            st[r]=a;
            actualizare_1(2*r);
        }
        if((st[2*r+1] < st[r]) && st[2*r+1] <= st[2*r])
        {
            poz[st[2*r+1]]=r;
            poz[st[r]]=2*r+1;
            int a=st[2*r+1];
            st[2*r+1]=st[r];
            st[r]=a;
            actualizare_1(2*r+1);
        }
    }
    else
    {
        if((st[2*r] < st[r]) && 2*r<=index)
        {
            poz[st[2*r]]=r;
            poz[st[r]]=2*r;
            int a=st[2*r];
            st[2*r]=st[r];
            st[r]=a;
            actualizare_1(2*r);
        }
    }
}
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        f>>x;
        if(x==1)
        {
            f>>t;
            q++;
            index++;
            v[q]=t;
            st[index]=t;
            poz[t]=index;
            actualizare(index);
        }
        if(x==2)
        {
            f>>t;
            st[poz[v[t]]]=st[index];
            poz[st[index]]=poz[v[t]];
            index--;
            actualizare(poz[st[index+1]]);
            actualizare_1(poz[st[index+1]]);
        }
        if(x==3)
            g<<st[1]<<'\n';
    }

    return 0;
}