let h = ref 0

let parent i = int_of_float (floor (float_of_int i) /. 2.)

let left i = 2*i

let right i = 2*i + 1

let swap i j t = let tmp = t.(i) in t.(i) <- t.(j); t.(j) <- tmp

let extract (t : int array) =
  let rec max_heapify i =
    let l = left i in
    let r = right i in
    let m = if l <= !h && t.(l) > t.(i) then l else i in
    let m = if r <= !h && t.(r) > t.(m) then r else m in
    if i <> m then begin
      swap i m t;
      max_heapify m
    end in
  let ret = t.(1) in
  t.(1) <- t.(!h);
  decr h;
  max_heapify 1;
  ret

let insert x (t : int array) =
  let rec doit i =
    if i > 1 && t.(parent i) < t.(i) then begin
      swap i (parent i) t;
      doit (parent i)
    end in
  incr h;
  t.(!h) <- x;
  doit !h

let split str delim =
  let open String in
  let rec doit s acc =
    match
      try Some (rindex s delim) with _ -> None
    with
    | None -> s :: acc
    | Some i -> doit (sub s 0 i) (sub s (i + 1) (length s - i - 1) :: acc) in
  doit str []

let () =
  let t = Array.make 2000001 0 in
  let rec doit () =
    match split (read_line ()) ' ' with
    | ["extract"] -> Printf.printf "%d\n%!" (extract t); doit ()
    | ["insert"; n] -> insert (int_of_string n) t; doit ()
    | _ -> () in
  doit ()