#include <cstdio>
#include <algorithm>
#define DIM 200020
using namespace std;
FILE *fin=freopen("heapuri.in","r",stdin);
FILE *fout=freopen("heapuri.out","w",stdout);

int pos[DIM], heap[DIM], timp[DIM];
int n, m, nr;

inline int father(int nod)
{
    return nod / 2;
}

inline int left_son(int nod)
{
    return nod * 2;
}

inline int right_son(int nod)
{
    return nod * 2 + 1;
}

inline void percolate(int n, int k)
{
    int key = heap[k], tt, pp;
    tt = timp[k];

    while( k > 1 && key < heap[ father(k) ] )
    {
        heap[k] = heap[father(k)];
        timp[k] = timp[father(k)];
        pos[timp[k]] = k;
        k = father(k);
    }

    heap[k] = key;
    pos[tt] = k;
    timp[k] = tt;
}

inline void sift(int n, int k)
{
    int son, tt = timp[k];
    do
    {
        son = 0;
        if( left_son(k) <= n )
        {
            son = left_son(k);
            if( right_son(k) <= n && heap[ right_son(k) ] < heap[ left_son(k) ] )
                son = right_son(k);
            if( heap[son] >= heap[k] )
                son = 0;
        }

        if( son )
        {
            timp[k] = timp[son];
            pos[timp[k]] = k;
            timp[son] = tt;
            pos[tt] = son;

            swap( heap[k], heap[son] );
            k = son;
        }

    }while( son );
}

void Solve()
{
    int op, a, b;
    scanf("%d", &m);

    for(int i = 1; i <= m; ++i)
    {
        scanf("%d", &op);

        if( op == 1 )
        {
            scanf("%d ", &a);
            ++nr, ++n;
            heap[n] = a;
            timp[n] = nr;
            pos[nr] = n;
            percolate(n, n);
        }

        else if( op == 2 )
        {
            scanf("%d", &a);
            a = pos[a];
            heap[a] = heap[n];
            pos[timp[n]] = a;
            timp[a] = timp[n];

            --n;

            if( a > 1 && heap[a] < heap[father(a)])
                percolate(n, a);
            else
                sift(n, a);
        }

        else
            printf("%d\n", heap[1]);

        //for(int j = 1; j <= n; ++j)
         //   printf("%d ", heap[j]);
       // printf("\n");
    }
}

int main()
{
    Solve();
    return 0;
}