#include <fstream>

using namespace std;


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

int st[200001],v[200001],poz[200001],index,x,n,t,q;
void actualizare(int r)
{
    while(r/2)
    {
        if(v[st[r]] < v[st[r/2]])
        {
            poz[st[r]]=r/2;
            poz[st[r/2]]=r;
            swap(st[r], st[r/2]);
        }
        else
            break;
        r=r/2;
    }
}
void actualizare_1(int r)
{
    if(2*r+1<=index)
    {
        if((v[st[2*r]] < v[st[r]]) && v[st[2*r]] <= v[st[2*r+1]])
        {
            poz[st[2*r]]=r;
            poz[st[r]]=2*r;
            swap(st[r], st[2*r]);
            actualizare_1(2*r);
        }
        if((v[st[2*r+1]] < v[st[r]]) && v[st[2*r+1]] <= v[st[2*r]])
        {
            poz[st[2*r+1]]=r;
            poz[st[r]]=2*r+1;
            swap(st[r], st[2*r+1]);
            actualizare_1(2*r+1);
        }
    }
    else
    {
        if((v[st[2*r]] < v[st[r]]) && 2*r<=index)
        {
            poz[st[2*r]]=r;
            poz[st[r]]=2*r;
            swap(st[r], st[2*r]);
            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]=q;
            poz[q]=index;
            actualizare(index);
        }
        if(x==2)
        {
            f>>t;
            st[poz[t]]=st[index];
            poz[st[index]]=poz[t];
            index--;
            actualizare(poz[st[index+1]]);
            actualizare_1(poz[st[index+1]]);
        }
        if(x==3)
            g<<v[st[1]]<<'\n';
    }

    return 0;
}