#include <fstream>

using namespace std;
ifstream f("heapuri.in");
ofstream g("heapuri.out");
long long j,n,t,x,y,z,k,m,i,poz[200010],heap[200010],v[200010];
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        heap[i]=1000000010;
    heap[0]=-1000000010;
    k=0;
    i=0;
    for(j=1;j<=n;j++)
    {
        f>>t;
        if(t==3)
            g<<heap[1]<<'\n';
        else
            if(t==1)
            {
                f>>x;
                v[++i]=x;
                heap[++k]=x;
                poz[x]=k;
                while(x<heap[poz[x]/2])
                {
                    m=heap[poz[x]/2];
                    heap[poz[x]/2]=x;
                    heap[poz[x]]=m;
                    poz[m]=poz[x];
                    poz[x]/=2;
                }
            }
            else
            {
                f>>x;
                heap[poz[v[x]]]=heap[k];
                poz[heap[k]]=poz[v[x]];
                x=heap[k];
                heap[k]=1000000010;
                k--;
                y=0;
                while(x<heap[poz[x]/2])
                {
                    m=heap[poz[x]/2];
                    heap[poz[x]/2]=x;
                    heap[poz[x]]=m;
                    poz[m]=poz[x];
                    poz[x]/=2;
                }
                while(x>heap[poz[x]*2]||x>heap[poz[x]*2+1])
                {
                    if(x>heap[poz[x]*2]&&x>heap[poz[x]*2+1])
                    {
                        if(heap[poz[x]*2]<heap[poz[x]*2+1])
                            y=1;
                        else
                            y=2;
                    }
                    if(x>heap[poz[x]*2]&&y!=2)
                    {
                        m=heap[poz[x]*2];
                        heap[poz[x]*2]=x;
                        heap[poz[x]]=m;
                        poz[m]=poz[x];
                        poz[x]*=2;
                    }
                    else
                    {
                        m=heap[poz[x]*2+1];
                        heap[poz[x]*2+1]=x;
                        heap[poz[x]]=m;
                        poz[m]=poz[x];
                        poz[x]*=2;
                        poz[x]++;
                    }
                    y=0;
                }
            }
    }
    return 0;
}