#include <cstdio>
#include <algorithm>

using namespace std;

struct heap
{
    int x,ind;
}h[200010];
int poz[200010],nr;

void interschimba(int nod1,int nod2)
{
    swap(h[nod1],h[nod2]);
    swap(poz[h[nod1].ind],poz[h[nod2].ind]);
}

void up_heap(int nod)
{
    while(nod>1 && h[nod/2].x>h[nod].x)
    {
        interschimba(nod,nod/2);
        nod=nod/2;
    }
}

void down_heap(int nod)
{
    while((nod*2<=nr && h[nod].x>h[nod*2].x) || (nod*2+1<=nr && h[nod].x>h[nod*2+1].x))
    {
        if(nod*2==nr || h[nod*2].x<h[nod*2+1].x)
        {
            interschimba(nod,nod*2);
            nod=nod*2;
        }
        else
        {
            interschimba(nod,nod*2+1);
            nod=nod*2+1;
        }
    }
}

int main()
{
    freopen("heapuri.in", "r", stdin);
    freopen("heapuri.out", "w", stdout);
    int n,cnt=0,tip,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&tip);
        if(tip==1)
        {
            scanf("%d",&x);
            h[++nr]={x,++cnt};
            poz[cnt]=nr;
            up_heap(nr);
        }
        else if(tip==2)
        {
            scanf("%d",&x);
            h[poz[x]]=h[nr];
            poz[h[nr].ind]=poz[x];
            up_heap(poz[x]);
            down_heap(poz[x]);
        }
        else printf("%d\n",h[1].x);
    }
    return 0;
}