#include <fstream>
#define N 200001
using namespace std;
ifstream in("heapuri.in");
ofstream out("heapuri.out");

int n, cod, x, nr, nn, l, Heap[N], pos[N], v[N];

void up(int x){
    while(x && v[Heap[x]] < v[Heap[x/2]])
    {
        swap(Heap[x], Heap[x/2]);
        swap(pos[Heap[x]], pos[Heap[x/2]]);
        x/=2;
    }
}

void down(int x){
    int y;
    while(x!=y)
    {
        y=x;
        if(2*y<=nr && v[Heap[2*y]]<v[Heap[x]])
            x=2*y;
        if(2*y+1<=nr && v[Heap[2*y+1]]<v[Heap[x]])
            x=2*y+1;
        swap(pos[Heap[x]], pos[Heap[y]]);
        swap(Heap[x], Heap[y]);
    }
}

int main()
{
    in>>n;
    for(int i=0;i<n;++i)
    {
        in>>cod;
        if(cod==1){
            in>>x;
            v[++l]=x;
            Heap[++nr]=l;
            pos[l]=nr;
            up(x);
        }
        if(cod==2){
            in>>x;
            nn = Heap[nr];
            swap(Heap[pos[x]], Heap[nr]);
            swap(pos[Heap[pos[x]]], pos[Heap[nr]]);
            nr--;
            up(pos[nn]);
            down(pos[nn]);
        }
        if(cod==3) out<<v[Heap[1]]<<'\n';
    }
    return 0;
}