#include <cstdio>
#include <algorithm>
#define Nmax 200010

using namespace std;

struct nod
{
    int val,poz;
};

nod H[Nmax];
int n,i,j,cod,pos[Nmax],x,nr,k;

inline void HeapUp(int k)
{
    int t;
    if (k<=1) return;
    t=k/2;
    if (H[k].val<H[t].val)
    {
        swap(H[k].val,H[t].val);
        swap(H[k].poz,H[t].poz);
        swap(pos[H[k].poz],pos[H[t].poz]);
        HeapUp(t);
    }
}

inline void HeapDown(int r, int k)
{
    int St,Dr,i;
    if (2*r<=k)
    {
        St=H[2*r].val;
        if (2*r+1<k) Dr=H[2*r+1].val;
        else Dr=St+1;

        if (St<Dr) i=2*r;
        else i=2*r+1;

        if (H[r].val>H[i].val)
        {
            swap(H[r].val,H[i].val);
            swap(H[r].poz,H[i].poz);
            swap(pos[H[r].poz],pos[H[i].poz]);
            HeapDown(i,k);
        }
    }
}

int main()
{
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);

    scanf("%d", &n);
    for (i=1; i<=n; ++i)
    {
        scanf("%d", &cod);
        if (cod==1)
        {
            ++k;
            nr++;
            pos[nr]=k;
            scanf("%d", &x);
            H[k].val=x;
            H[k].poz=nr;
            HeapUp(k);
        }
        else if (cod==2)
        {

            scanf("%d", &x);
            int aux=pos[x];
            int r=pos[x];
            swap(H[r].val,H[k].val);
            swap(H[r].poz,H[k].poz);
            swap(pos[H[r].poz],pos[H[k].poz]);

            k--;

            HeapDown(aux,k);


        }
        else printf("%d\n", H[1].val);
    }

    return 0;
}