#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("heapuri.in");
ofstream fout("heapuri.out");

int heap[200010], elem[200010], poz[200010];
int N, L, NR;

void push(int x)
{
    while(x/2 && elem[heap[x]] < elem[heap[x/2]])
    {
        swap(heap[x], heap[x/2]);

        poz[heap[x]] = x;
        poz[heap[x/2]] = x/2;
        x/=2;
    }
}

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

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

        swap(heap[x], heap[y]);
        poz[heap[x]] = x;
        poz[heap[y]] = y;
    }
}


int main()
{
    int n, op, x;
    fin>>n;
    for(int i=0; i<n; i++)
    {
        fin>>op;

        if(op<3) fin>>x;

        switch(op)
        {
        case 1:
        {
            L++;
            NR++;

            elem[NR] = x;
            heap[L] = NR;
            poz[NR] = L;

            push(L);
            break;
        }
        case 2:
        {
            elem[x] = -1;

            push(poz[x]);

            poz[heap[1]] = 0;
            heap[1] = heap[L--];
            poz[heap[1]] = 1;
            if(L>1) pop(1);


            break;
        }
        case 3:
        {
            fout<<elem[heap[1]]<<"\n";
            break;
        }
        default:
        {
            break;
        }
        }
    }
}