Program heapu;
var a,heap,poz:array [0..200010] of longint;
    n,l,i,x,cod,nr,unu:longint;
    f,g:text;
  procedure push(x:longint);
  var aux:longint;
  begin
    aux:=0;
    while (x div 2>0) and (A[Heap[x]]<A[Heap[x div 2]]) do
      begin
        aux:=Heap[x];
        Heap[x]:=Heap[x div 2];
        Heap[x div 2]:=aux;
        Poz[Heap[x]]:=x;
        Poz[Heap[x div 2]]:=x div 2;
        x:=x div 2;
      end;
  end;
  procedure pop(x:longint);
  var aux,y:longint;
  begin
    y:=0;
    aux:=0;
    while (x<>y)do
      begin
        y:=x;
        if (y*2<=L) and (A[Heap[x]]>A[Heap[y*2]]) then
          x:=y*2;
        if (y*2+1<=L) and (A[Heap[x]]>A[Heap[y*2+1]]) then
          x:=y*2+1;
        aux:=Heap[x];
        Heap[x]:=Heap[y];
        Heap[y]:=aux;
        Poz[Heap[x]]:=x;
        Poz[Heap[y]]:=y;
      end;
  end;
begin
  assign(f,'heapuri.in');reset(f);
  assign(g,'heapuri.out');rewrite(g);
  readln(f,n);
  for i:=1 to n do
    begin
      read(f,cod);
      if cod=1 then
        begin
          inc(l);inc(nr);
          readln(f,x);
          a[nr]:=x;
          heap[l]:=nr;
          poz[nr]:=l;
          push(l);
        end
      else
        if cod=2 then
          begin
            readln(f,x);
            a[x]:=-1;
            push(poz[x]);
            poz[heap[1]]:=0;
            heap[1]:=heap[l];
            dec(l);
            poz[heap[1]]:=1;
            if l>1 then
              begin
                unu:=1;
                pop(unu);
              end;
          end
        else
          writeln(g,a[heap[1]]);
    end;
  close(f);
  close(g);
end.