class PriorityQueue
  class Error < StandardError; end

  def initialize(cap)
    @keys = Array.new(cap + 1)
    @pos = 0
  end

  def insert(key)
    @pos += 1
    @keys[@pos] = -Float::INFINITY
    increase_key(@pos, key)
  end

  def extract_max
    if @pos < 1
      raise Error, 'queue is empty'
    end

    max = @keys[1]
    @keys[1] = @keys[@pos]
    @pos -= 1
    max_heapify(1)

    max
  end

  private

  def parent(i)
    i / 2
  end

  def left(i)
    2 * i
  end

  def right(i)
    2 * i + 1
  end

  def increase_key(i, key)
    if key < @keys[i]
      raise Error, "new key (#{key}) is less than current key (#{@keys[i]})"
    end

    @keys[i] = key

    while i > 1 && @keys[parent(i)] < @keys[i]
      @keys[i], @keys[parent(i)] = @keys[parent(i)], @keys[i]
      i = parent(i)
    end
  end

  def max_heapify(i)
    l = left(i)
    r = right(i)

    largest = i

    if l <= @pos && @keys[l] > @keys[i]
      largest = l
    end

    if r <= @pos && @keys[r] > @keys[largest]
      largest = r
    end

    if largest != i
      @keys[i], @keys[largest] = @keys[largest], @keys[i]
      max_heapify(largest)
    end
  end
end

if $PROGRAM_NAME == __FILE__
  queue = PriorityQueue.new(2000000)

  while line = gets
    line = line.chomp

    break if line == 'end'

    command, key = line.split
    key = key.to_i if key

    case command
    when 'insert'
      queue.insert(key)
    when 'extract'
      puts queue.extract_max
    else
      raise "unknown command: #{command}"
    end
  end
end