var v:array [1..200000] of longint;
    w, z:array [1..200000] of longint;
    n, i, ii, j, x, y, aux, max:longint;
    f, g:text;

begin
assign (f, 'heapuri.in'); reset (f);
assign (g, 'heapuri.out'); rewrite (g);

read (f, n);
i:=1;
for ii := 1 to n do
  begin
  read (f, x);
  case x of
    1:begin
      read (f, y);
      j:=i;
      v[j]:=y; w[i]:=j; z[i]:=j;
      while (v[j]<v[j div 2]) and (j>1) do
        begin
        aux:= v[j]; v[j]:=v[j div 2]; v[j div 2]:=aux;
        aux:= z[w[j]]; z[w[j]]:= z[w[j div 2]]; z[w[j div 2]]:=aux;
        aux:= w[j]; w[j]:=w[j div 2]; w[j div 2]:=aux;
        j:=j div 2;
        end;
      i:=i+1;
      end;
    2:begin
      read (f, y);
      j:=z[y];
      while j <> 1 do
        begin
        aux:= v[j]; v[j]:=v[j div 2]; v[j div 2]:=aux;
        aux:= z[w[j]]; z[w[j]]:= z[w[j div 2]]; z[w[j div 2]]:=aux;
        aux:= w[j]; w[j]:=w[j div 2]; w[j div 2]:=aux;

        j:=j div 2;
        end;
      v[1]:=v[i-1]; j:=1;
      aux:= z[w[1]]; z[w[1]]:= z[w[i-1]]; z[w[i-1]]:=aux;
      aux:= w[1]; w[1]:=w[i-1]; w[i-1]:=aux;

      if v[2]>v[3] then max :=2 else max :=3;
      while (v[j] > v[max]) and (j< i div 2) do
        begin
        aux:= v[j]; v[j]:=v[max]; v[max]:=aux;
        aux:= z[w[j]]; z[w[j]]:= z[w[max]]; z[w[max]]:=aux;
        aux:= w[j]; w[j]:=w[max]; w[max]:=aux;

        if v[2*j]>v[2*j+1] then max := 2*j else max :=2*j+1;
        end;
      if v[j]>v[2*j] then
        begin
        aux:= v[j]; v[j]:=v[2*j]; v[2*j]:=aux;
        aux:= z[w[j]]; z[w[j]]:= z[w[j*2]]; z[w[j* 2]]:=aux;
        aux:= w[j]; w[j]:=w[j * 2]; w[j* 2]:=aux;

        end;
      end;
    3:begin
      writeln (g, v[1]);
      end;
    end;
  end;

close (f); close (g);
end.