Program Heapuri;
type Heap=record
       l : longint;
       a,t : array[0..200001] of longint;
     end;
var Intrare,Iesire : text;
    h : Heap;
    c : array[0..200001] of longint;
    n,count : longint;

procedure deschideFisiere;
begin
  assign(Intrare,'heapuri.in');
  reset(Intrare);
  assign(Iesire,'heapuri.out');
  rewrite(Iesire);
end;

procedure sw(var x,y : longint);
var aux : longint;
begin
  aux:=x;
  x:=y;
  y:=aux;
end;

procedure swap(var h : Heap; x,y : longint);
begin
  with h do begin
    c[t[x]]:=y;
    c[t[y]]:=x;
    sw(a[x],a[y]);
    sw(t[x],t[y]);
  end;
end;

function st(var h : Heap; x : longint) : longint;
begin
  if 2*x<=h.l then st:=2*x else st:=200001;
end;

function dr(var h : Heap; x : longint) : longint;
begin
  if 2*x+1<=h.l then dr:=2*x+1 else dr:=200001;
end;

procedure percolate(var h : Heap; x : longint);
begin
  while h.a[x div 2]>h.a[x] do begin
    swap(h,x,x div 2);
    x:=x div 2;
  end;
end;

procedure sift(var h : Heap; x : longint);
var s,d : longint;
begin
  s:=st(h,x);
  d:=dr(h,x);
  while s<200001 do begin
    if (h.a[s]<h.a[x]) or (h.a[d]<h.a[x]) then
     if h.a[s]<h.a[d] then begin
       swap(h,x,s);
       x:=s;
     end
     else begin
       swap(h,x,d);
       x:=d;
     end
    else break;
    s:=st(h,x);
    d:=dr(h,x);
  end;
end;

procedure adauga(var h : Heap; x : longint);
begin
  count:=count+1;
  h.l:=h.l+1;
  h.a[h.l]:=x;
  h.t[h.l]:=count;
  c[count]:=h.l;
  percolate(h,h.l);
end;

procedure sterge(var h : Heap; x : longint);
var k : longint;
begin
  k:=c[x];
  swap(h,k,h.l);
  h.l:=h.l-1;
  if h.a[k div 2]<h.a[k] then sift(h,k)
   else percolate(h,k);
end;

procedure proceseaza;
var op : byte;
    x,i : longint;
begin
  h.l:=0;
  h.a[0]:=-1;
  h.a[200001]:=maxlongint;
  count:=0;
  readln(Intrare,n);
  for i:=1 to n do begin
    read(Intrare,op);
    if op<3 then readln(Intrare,x);
    case op of
      1: adauga(h,x);
      2: sterge(h,x);
      3: writeln(Iesire,h.a[1]);
    end;
  end;
end;

procedure inchideFisiere;
begin
  close(Intrare);
  close(Iesire);
end;

begin
  deschideFisiere;
  proceseaza;
  inchideFisiere;
end.