class BinaryHeap
  def initialize
    @array = []
  end

  def add(obj)
    @array << obj
    sift_up(size - 1)
  end

  def swap(i, j)
    u = @array[i]
    v = @array[j]
    @array[i], @array[j] = v, u
  end

  def sift_up(i)
    return if i == 0
    j = (i - 1) / 2
    if @array[i] > @array[j]
      swap(i, j)
      sift_up(j)
    end
  end

  def shift
    min = @array[0]
    swap(0, size-1) if size > 1
    @array.pop
    sift_down(0) if size > 0
    min
  end

  def sift_down(i)
    j = 2 * i + 1
    k = j + 1
    return if j >= size
    if k >= size
      if @array[j] > @array[i]
        swap(i, j)
        sift_down(j)
      end
    else
      l = (@array[j] > @array[k] ? j : k)
      if @array[l] > @array[i]
        swap(i, l)
        sift_down(l)
      end
    end
  end

  def size
    @array.size
  end
end

queue = BinaryHeap.new
loop do
  command, value = gets.chomp.split
  case command
  when "end"
    break
  when "insert"
    queue.add(value.to_i)
  when "extract"
    p queue.shift
  end
end

