#include <bits/stdc++.h>

using namespace std;
ifstream f("heapuri.in");
ofstream g("heapuri.out");
int j,k,v[200010],n,heap[200010],pos[200010],a[200010],right,numar;
int lz;
void push(int x)
{
    while(x/2 and v[heap[x]]<v[heap[x/2]])
    {
        swap(heap[x],heap[x/2]);
        pos[heap[x]] = x;
        pos[heap[x/2]] = x/2;
        x = x/2;
    }
}
void pop(int x)
{
    int y=0;
    while(x!=y)
    {
        y=x;
        if(y*2<=lz and v[heap[x]]>v[heap[y*2]])
            x = y*2;
        if(y*2+1<=lz and v[heap[x]]>v[heap[y*2+1]])
            x = y*2+1;
        swap(heap[x],heap[y]);
        pos[heap[x]] = x;
        pos[heap[y]] = y;

    }
}
int main()
{
    int x,val,i;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>val;
        if(val<3)
        {
            f>>x;
        }
        if(val == 1)
        {
            lz++;
            numar++;
            v[numar] = x;
            heap[lz] = numar;
            pos[numar] = lz;
            push(lz);
        }
        if(val == 2)
        {
            v[x] = -1;
            if(pos[x] != 0 and x<=numar)
            push(pos[x]);
            pos[heap[1]] = 0;
            heap[1] = heap[lz--];
            pos[heap[1]] = 1;
            if(lz>1)
                pop(1);
        }
        if(val == 3)
            g<<v[heap[1]]<<endl;
    }
    return 0;
}