class PriorityQueue
  @@INF = 1.0 / 0
  #?????????
  def initialize
    @queue = Array.new(1)
    @queue[0] = -114514
  end

  #???????????????????´??????????
  def top
    @queue[1]
  end

  #???????????????????´??????????????????????????´??????????
  def pop
    return if @queue.size < 1
    top = @queue[1]
    @queue[1] = @queue[@queue.size - 1]
    @queue.pop
    max_heap(1)
    top
  end

  #?????\
  def push(n)
    @queue.push(n)
    @queue[@queue.size - 1] = -1 * @@INF
    increase_key(@queue.size - 1,n)
  end

  #????????????????
  def empty?
    @queue.size == 1
  end

  #????´???°
  def size
    @queue.size - 1
  end

  #?????\?????????
  def increase_key(i,key)
    return if key < @queue[i]
    @queue[i] = key
    while i > 1 && @queue[i / 2] < @queue[i] do
      @queue[i],@queue[i / 2] = @queue[i / 2],@queue[i]
      i = i / 2
    end
  end

  #?????§???
  def max_heap(i)
    l = 2 * i
    r = 2 * i + 1
    if l< @queue.size && @queue[l] > @queue[i] then largest = l
    else largest = i end
    largest = r if r < @queue.size && @queue[r] > @queue[largest]
    if largest != i then
      @queue[i],@queue[largest] = @queue[largest],@queue[i]
      max_heap(largest)
    end
  end

  #?????§?????´??°
  def build_max_heap!
    return if @queue.size == 2
    (@queue.size / 2).downto(1) do |i|
      max_heap(i)
    end
  end
end

pq = PriorityQueue.new
loop do
  input = gets.split
  if input[0][0] == "i" then
    pq.push(input[1].to_i)
  elsif input[0] == "extract" then
    puts pq.pop
  else
    break
  end
end
