var i,j:longint;nheap,n,m:int64;
    fi,fo:text;
    a:array[0..300000,0..2] of int64;
    mot,t,heap:array[0..300000] of int64;
    cx:array[0..300000] of boolean;
procedure nhap;
begin
    assign(fi,'heapuri.in');
    reset(fi);
    assign(fo,'heapuri.out');
    rewrite(fo);
    readln(fi,n);
    j:=0;
    for i:=1 to n do
       begin
          read(fi,a[i,1]);
          if a[i,1]<>3 then readln(fi,a[i,2]);
       end;
end;
procedure swap(var c,d:int64);
var tg:int64;
begin
   tg:=c;
   c:=d;
   d:=tg;
end;
procedure upheap(k:longint);
begin
   if (k=1) or (heap[k div 2]<=heap[k]) then exit;
   swap(heap[k],heap[k div 2]);
   swap(mot[t[k]],mot[t[k div 2]]);
   swap(t[k],t[k div 2]);
   upheap(k div 2);
end;
procedure downheap(k:longint);
begin
   m:=2*k;
   if m>nheap then exit;
   if (heap[m]>heap[m+1]) and (m+1<=nheap) then inc(m);
   if heap[k]>heap[m] then
      begin
             swap(heap[k],heap[m]);
             swap(mot[t[k]],mot[t[m]]);
             swap(t[k],t[m]);
             downheap(m);
      end;
end;
procedure push(k:longint);
begin
   inc(nheap);
   t[nheap]:=j;
   mot[j]:=nheap;
   heap[nheap]:=k;
   upheap(nheap);
end;
function pop(k:longint):int64;
begin
   pop:=heap[k];
   heap[k]:=heap[nheap];
   mot[t[nheap]]:=mot[t[k]];
   t[k]:=t[nheap];
   dec(nheap);
   if (k=1) or (heap[k]>=heap[k div 2]) then downheap(k)
     else upheap(k);
end;
begin
   nhap;
   nheap:=0;
   fillchar(cx,sizeof(cx),true);
   for i:=1 to n do
       begin
           if a[i,1]=1 then
              begin
                  inc(j);
                  push(a[i,2]);
              end;
           if a[i,1]=3 then
               begin
                 cx[t[1]]:=false;
                 writeln(fo,pop(1));
               end;
           if (a[i,1]=2) and (cx[a[i,2]]=true) then m:=pop(mot[a[i,2]]);
       end;
   close(fo);
end.