#include<iostream>
#include<fstream>
#include <assert.h>
using namespace std;
#define maxn 200010

int n,l,nr,a[maxn],heap[maxn],pos[maxn];

void push(int x)
{
    int aux;
    while (x/2&&a[heap[x]]<a[heap[x/2]])
    {
        aux = heap[x];
        heap[x] = heap[x/2];
        heap[x/2] = aux;
        pos[heap[x]] = x;
        pos[heap[x/2]] = x/2;
        x /= 2;
    }
}

void pop(int x)
{
    int aux, y = 0;
    while (x!=y)
    {
        y = x;

        if (y*2<=l&&a[heap[x]]>a[heap[y*2]]) x = y*2;
        if (y*2+1<=l&&a[heap[x]]>a[heap[y*2+1]]) x = y*2+1;

        aux=heap[x];
        heap[x]=heap[y];
        heap[y]=aux;

        pos[heap[x]]=x;
        pos[heap[y]]=y;
    }
}

int main()
{
    ifstream f("heapuri.in");
    ofstream g("heapuri.out");

    int i, x, cod;

    f>>n;

    assert(1<=n&&n<=200000);

    for (i=1;i<=n;i++)
    {
        f>>cod;
        assert(1<=cod&&cod<=3);
        if (cod<3)
        {
            f>>x;
            assert(1<=x&&x<=1000000000);
        }

        if (cod==1)
        {
            l++; nr++;
            a[nr]=x;
            heap[l]=nr;
            pos[nr]=l;
            push(l);
        }

        if (cod==2)
        {
            a[x]=-1;
            assert(pos[x]!=0);
            assert(1<=x&&x<=nr);
            push(pos[x]);

            pos[heap[1]]=0;
            heap[1]=heap[l--];
            pos[heap[1]]=1;
            if(l>1) pop(1);
        }

        if (cod == 3) g<<a[heap[1]]<<"\n";
    }
    f.close();
    g.close();
    return 0;
}