#include <stdio.h>
#include <algorithm>
using namespace std;
const int nmax = 200005;

int n, i, t, x, q, k, h[nmax], nr[nmax], poz[nmax];

void down(int i)
{
    int fiu;
    while((i<<1)<=q)
    {
        fiu=i<<1;
        if ((int)(fiu|1)<=q)
            if (h[fiu|1]<h[fiu])fiu|=1;
        if (h[fiu]<h[i])
        {
            swap(h[i], h[fiu]);
            swap(nr[i], nr[fiu]);
            poz[nr[i]]=i;
            poz[nr[fiu]]=fiu;
            i=fiu;
        }
        else break;
  }
}

void up(int i)
{
    int val=h[i],valnr=nr[i];
    while (i>1 && val<h[i>>1])
    {
        h[i]=h[i>>1];
        nr[i]=nr[i>>1];
        poz[nr[i]]=i;
        i=i>>1;
    }
    h[i]=val;
    nr[i]=valnr;
    poz[nr[i]]=i;
}

int main()
{
    freopen("heapuri.in", "r", stdin);
    freopen("heapuri.out", "w", stdout);
    scanf("%ld", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%ld", &t);
        if (t==3) printf("%d\n", h[1]);
        else if (t==1)
        {
            scanf("%ld",&x);
            h[++q]=x;
            nr[q]=++k;
            poz[k]=q;
            up(q);
        }
        else
        {
            scanf("%d",&x);
            h[poz[x]]=h[q];
            q--;
            down(poz[x]);
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}