#include <iostream>
#include <cstdio>
#define inf 1000000050

using namespace std;

int heap[400050];
int v[200050];
int poz[200050];

void upheap(int node)
{
    if(node!=1 && v[heap[node]]<v[heap[node/2]])
    {
        poz[heap[node]]=node/2;
        poz[heap[node/2]]=node;
        swap(heap[node],heap[node/2]);
        upheap(node/2);
    }
}

void downheap(int node)
{

    if(v[heap[node]]>min(v[heap[2*node]],v[heap[2*node+1]]))
    {
        if(v[heap[2*node]]>v[heap[2*node+1]])
        {
            poz[heap[node]]=2*node+1;
            poz[heap[2*node+1]]=node;
            swap(heap[node],heap[2*node+1]);
            downheap(2*node+1);
        }
        else
        {
            poz[heap[node]]=2*node;
            poz[heap[2*node]]=node;
            swap(heap[node],heap[2*node]);
            downheap(2*node);
        }
    }
}

int main()
{
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);
    int n,i,p,x,k=0,j=0;
    scanf("%d",&n);
    v[0]=inf;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&p);
        if(p==1)
        {
            j++;
            scanf("%d",&v[j]);
            k++;
            heap[k]=j;
            poz[j]=k;
            upheap(k);
        }
        else if(p==2)
        {
            scanf("%d",&x);
            heap[poz[x]]=heap[k];
            heap[k]=0;
            k--;
            downheap(poz[x]);
        }
        else
            printf("%d\n",v[heap[1]]);
    }
    return 0;
}