def insert(array, new_value)
  array << new_value
  current = array.size-1
  parent = current / 2
  while (parent > 0) do
    if (array[parent] < array[current]) then
      array[parent], array[current] = array[current], array[parent]
      current = parent
      parent = current / 2
    else
      break
    end
  end
end

def extract(array)
  return nil if array.size == 1
  array[1], array[-1] = array[-1], array[1]
  max = array.pop

  current = 1
  loop do
    bigger_child = get_bigger_child(array, current)
    break if bigger_child == nil
    break if array[current] >= bigger_child[0]
    array[current], array[bigger_child[1]] = array[bigger_child[1]], array[current]
    current = bigger_child[1]
  end

  return max
end

def get_bigger_child(array, i)
  return nil if array.size <= i*2
  return [array[i*2], i*2] if array.size == (i*2 + 1)

  left = [array[i*2], i*2]
  right = [array[i*2+1], i*2+1]
  return [left, right].max_by{|x| x[0]}
end


# main
array = [nil]
while line = gets do
  inputs = line.chomp.split
  if (inputs[0] == 'insert') then
    insert(array, inputs[1].to_i)
  elsif (inputs[0] == 'extract') then
    puts extract(array)
  else
    break
  end
end