class PairingHeap
  attr_reader :node
  def initialize(node=nil)
    @node=node
  end
  def find_min
    if @node
      @node[0]
    else
      raise "no node"
    end
  end
  def merge(heap)
    if !@node
      @node=heap.node
    elsif !heap.node
      nil
    elsif @node[0] > heap.node[0]
      @node[1]=[heap]+@node[1]
    else
      @node=[heap.node[0],[PairingHeap.new(@node)]+heap.node[1]]
    end
    self
  end
  def insert(elem)
    merge(PairingHeap.new([elem,[]]))
  end
  def delete_min
    if @node
      @node=(@node[1].each_slice(2).map{|i,j|i.merge(j||PairingHeap.new)}.inject(&:merge)||PairingHeap.new).node
    else
      raise "no node"
    end
  end
  def inspect
    if @node
      "["+@node[0].to_s+","+@node[1].map(&:inspect)*","+"]"
    else
      "no node"
    end
  end
end


pq=PairingHeap.new
while gets
  op,arg = $_.split
  case op
  when "insert"
    pq.insert arg.to_i
  when "extract"
    p pq.find_min
    pq.delete_min
  when "end"
  end
end