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

begin
assign (f, 'heapuri.in'); settextbuf (f, buf1); reset (f);
assign (g, 'heapuri.out'); settextbuf (g, buf2); 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}
      readln (f, y);
      i:=i+1; l:=l+1;
      j:=i;
      v[j]:=y; w[i]:=l; z[l]:=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
      readln (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;

      if (j <> 1) and (v[j]<v[j div 2]) then
        begin
        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;
        end
                                         else
        begin
        max:=1;
        while (max<>0) do
          begin
          max:=0;

          if j*2<=i then
            begin
            max:=j*2;
            if (j*2+1<i) and (v[j*2+1]<v[j*2]) then max := j*2+1;
            if v[j] < v[max] then
              begin
              max:=0;
              end;
            end;
          if max <> 0 then
            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;
            end;
          j:=max;;
          end;
        end;
      end;
    3:begin
      writeln (g, v[1]);
      end;
    end;
  end;

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