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

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

read (f, n);
i:=0; l:=0;
for ii := 1 to n do
  begin
  read (f, x);
  case x of                         {l tine contorul la al catalea numar intr}
    1:begin                         {i tine contnrul la cate numere sunt in sir}
      read (f, y);
      i:=i+1; l:=l+1;
      j:=i;
      v[j]:=y; w[i]:=l; z[l]:=j;    {era 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:= w[j]; w[j]:=w[j div 2]; w[j div 2]:=aux;
        aux:= z[w[j]]; z[w[j]]:= z[w[j div 2]]; z[w[j div 2]]:=aux;
        j:=j div 2;
        end;
      end;
    2:begin
      read (f, y);
      j:=z[y];
      v[j]:=v[i];
      aux:= w[j]; w[j]:=w[i]; w[i]:=aux;
      aux:= z[w[j]]; z[w[j]]:= z[w[i]]; z[w[i]]:=aux;
      i:=i-1;

      while (j <> 1) and (v[j]<v[j div 2]) 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;

      if v[j*2]<v[j*2+1] then max :=j*2 else max :=j*2+1;
      while (v[j] > v[max]) and (max<= i) do
        begin
        aux:= v[j]; v[j]:=v[max]; v[max]:=aux;
        aux:= w[j]; w[j]:=w[max]; w[max]:=aux;
        aux:= z[w[j]]; z[w[j]]:= z[w[max]]; z[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]) and (j*2=i) then
//        begin
 //       aux:= v[j]; v[j]:=v[2*j]; v[2*j]:=aux;
//        aux:= w[j]; w[j]:=w[j * 2]; w[j* 2]:=aux;
//        aux:= z[w[j]]; z[w[j]]:= z[w[j*2]]; z[w[j* 2]]:=aux;

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

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