#include<cstdio>
#include<algorithm>

using namespace std;

int heap[200010],sz,nums;
int value_inserted_at[200010];
int pos_in_heap[200010];
int n;

void up_heap(int nod)
{
    if(value_inserted_at[heap[nod/2]]>value_inserted_at[heap[nod]])
    {
        swap(heap[nod/2],heap[nod]);
        swap(pos_in_heap[heap[nod]],pos_in_heap[heap[nod/2]]);
        up_heap(nod/2);
    }
}

void down_heap(int nod)
{
    if(nod*2<=sz)
    {
        //printf("!!! %d %d\n",nod,sz);
        //printf(" %d\n%d %d\n",value_inserted_at[heap[nod]],value_inserted_at[heap[nod*2]],value_inserted_at[heap[nod*2+1]]);
        if(nod*2+1<=sz)
        {
            if(value_inserted_at[heap[nod*2]]<value_inserted_at[heap[nod*2+1]])
            {
                if(value_inserted_at[heap[nod]]>value_inserted_at[heap[nod*2]])
                {
                    swap(heap[nod*2],heap[nod]);
                    swap(pos_in_heap[heap[nod]],pos_in_heap[heap[nod*2]]);
                    down_heap(nod*2);
                }
            }
            else if(value_inserted_at[heap[nod]]>value_inserted_at[heap[nod*2+1]])
            {
                swap(heap[nod*2+1],heap[nod]);
                swap(pos_in_heap[heap[nod]],pos_in_heap[heap[nod*2+1]]);
                down_heap(nod*2+1);
            }
        }
        else if(value_inserted_at[heap[nod]]>value_inserted_at[heap[nod*2]])
        {
            swap(heap[nod*2],heap[nod]);
            swap(pos_in_heap[heap[nod]],pos_in_heap[heap[nod*2]]);
            down_heap(nod*2);
        }
    }
}

int main()
{
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);

    scanf("%d",&n);
    int type,x;
    int lg=1;
    for(int i=1;i<=n;i++)
    {

        scanf("%d",&type);
        //printf("@%d@\n",type);
        if(type==1)
        {
            scanf("%d",&x);
            nums++;
            sz++;
            heap[sz]=nums;
            value_inserted_at[nums]=x;
            pos_in_heap[nums]=sz;

            up_heap(sz);
        }
        else if(type==2)
        {
            scanf("%d",&x);
            swap(heap[sz],heap[pos_in_heap[x]]);
            pos_in_heap[heap[pos_in_heap[x]]]=pos_in_heap[x];
            sz--;
            //printf(">***\n");
            down_heap(pos_in_heap[heap[pos_in_heap[x]]]);
            //printf("***<\n");
        }
        else
        {
            printf("%d\n",value_inserted_at[heap[1]]);
        }

        /*lg=1;
        for(int i=1;i<=sz;i++)
        {
            if(i==lg)
            {
                printf("\n");
                lg<<=1;
            }
            printf("%d ",value_inserted_at[heap[i]]);
        }
        printf("\n\n");*/
    }
}