program HEAPURI;
Const
        fi='HEAPURI.IN';
        fo='HEAPURI.OUT';
Var N,i,j,Nheap,k,u,v:longint;
    HEAP,a,b,c,vt:array[1..200010] of longint;
    visited:array[1..200010] of boolean;

    procedure Swap(var x,y:longint);
    Var tg:longint;
    begin
            tg:=x;
            x:=y;
            y:=tg;
    end;

    procedure UPHEAP(i:longint);
    begin
            IF (i=1) or (heap[i]>=heap[i div 2]) then exit;
            Swap(heap[i],heap[i div 2]);
            Swap(vt[heap[i]],vt[heap[i div 2]]);
            Upheap(i div 2);
    end;

    procedure DOWNHEAP(i:longint);
    Var j:longint;
    begin
            j:=2*i;
            If j>Nheap then exit;
            IF heap[j]>heap[j+1] then inc(j);
            If heap[i]>heap[j] then
            begin
                   Swap(heap[i],heap[j]);
                   Swap(vt[heap[i]],vt[heap[j]]);
                   DOWNHEAP(j);
            end;
    end;

    procedure PUSH(x:longint);
    begin
            inc(Nheap);heap[Nheap]:=x;
            vt[x]:=nheap;
            Upheap(Nheap);
    end;

    Function POP(x:longint):longint;
    begin
            visited[heap[x]]:=true;
            Pop:=heap[x];
            heap[x]:=heap[nheap];
            Dec(Nheap);
            Downheap(x);
    end;

    procedure input;
    Var f:text;
    begin
           Assign(f,fi);Reset(f);
           Nheap:=0;k:=0;v:=0;
           Fillchar(visited,Sizeof(visited),false);
           Readln(f,N);
           For i:=1 to N do
           begin
                    Read(f,a[i]);
                    IF A[i]=1 then
                    begin
                           inc(v);
                           readln(f,b[v]);
                           Push(B[v]);
                    end;
                    IF A[i]=2 then
                    begin
                           readln(f,u);
                           If not visited[b[u]] then  Pop(vt[B[u]]);
                    end;
                    IF A[i]=3 then
                    begin
                           readln(f);
                           inc(k);
                           C[k]:=Pop(1);
                    end;
           end;
           close(f);
    end;

    procedure output;
    Var f:text;
    begin
           Assign(f,fo);Rewrite(f);
           For i:=1 to K do Writeln(f,C[i]);
           close(f);
    end;

BEGIN
           input;
           output;
END.