#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,poz,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],H[t]);
        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],H[i]);
             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(poz);
        }
        else if (cod==2)
        {

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

             k--;

                HeapDown(aux,k);


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

    return 0;
}