#include<cstdio>
#include<cassert>
#define maxn 200010

using namespace std;


int N, L, NR;
int v[maxn], Heap[maxn], Pos[maxn];

void percolate( int );
void sift( int );


int main()
    {
        int i, t, x, xx;

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

        scanf("%d", &N);
        assert(1 <= N && N <= 200000);

        for ( i = 1; i <= N; i++)
        {
            scanf("%d", &t);
            assert(1 <= t && t <= 3);

            if ( t < 3)
            {
                scanf("%d", &x);
                assert(1 <= x && x<=1000000000);
            }

            if ( t == 1)
            {
                L++, NR++;
                v[NR] = x;
                Heap[L] = NR;
                Pos[NR] = L;

                percolate(L);
            }

            if ( t == 2)
            {
                xx = x;
                assert(Pos[x] != 0);
                assert(1<=x && x<=NR);
                v[x] = v[Heap[L--]];

                percolate(Pos[x]);
                sift(Pos[x]);

            }
            if (t == 3) printf("%d\n", v[Heap[1]]);

            //printf("\n\nNR=%d L=%d\n\n", NR, L);
        }
    }

void percolate(int x)
{
    int aux;

    while ( x/2 && v[ Heap[x] ] < v[ 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 sift(int x)
{
    int aux, y = 0;


    while ( x != y)
    {
        y = x;

        if ( y*2 <= L && v[Heap[x]] > v[Heap[y*2]]) x = y*2;
        if ( y*2 + 1 <= L && v[Heap[x]] > v[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;
    }
}