#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/2!=0 && v[heap[node]]<v[heap[node/2]])
    {
        swap(poz[heap[node]],poz[heap[node/2]]);
        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]])
        {
            swap(poz[heap[node]],poz[heap[2*node+1]]);
            swap(heap[node],heap[2*node+1]);
            downheap(2*node+1);
        }
        else
        {
            swap(poz[heap[node]],poz[heap[2*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;
    scanf("%d",&n);
    v[0]=inf;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&p);
        if(p==1)
        {
            scanf("%d",&v[i]);
            k++;
            heap[k]=i;
            poz[i]=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;
}