class MaxHeap
  def initialize
    @heap = [nil]
    @size = 0
  end
  
  def insert(key)
    @heap << key
    @size += 1
    up_heap(@size / 2)
  end
  
  def up_heap(i)
    return if i.zero?
    l, r = i * 2, i * 2 + 1
    largest = (l <= @size and @heap[l] > @heap[i]) ? l : i
    largest = r if r <= @size and @heap[r] > @heap[largest]
    unless largest == i
      @heap[i], @heap[largest] = @heap[largest], @heap[i]
      up_heap(i / 2)
    end
  end
  
  def remove_root
    a = @heap[1]
    @heap[1] = @heap.pop
    @size -= 1
    down_heap(1)
    a
  end
  
  def down_heap(i)
    return if i > @size
    l, r = i * 2, i * 2 + 1
    largest = (l <= @size and @heap[l] > @heap[i]) ? l : i
    largest = r if r <= @size and @heap[r] > @heap[largest]
    unless largest == i
      @heap[i], @heap[largest] = @heap[largest], @heap[i]
      down_heap(largest)
    end
  end
end


h = MaxHeap.new

$<.readlines.map {|l| l.chomp.split}.each do |command|
  case command[0]
  when "insert" then h.insert(command[1].to_i)
  when "extract" then puts h.remove_root
  when "end" then break
  else raise "error"
  end
end

