class PriorityQueue
	ROOT_INDEX = 0
	
	def initialize
		@heap = []
	end

	def insert(key)
		@heap << key
		bottom_up_adjust(@heap.size - 1)
		self
	end

	def extract
		result = @heap.shift
		top_down_adjust(ROOT_INDEX)
		result
	end

	def to_s
		@heap.to_s
	end

	private
	def bottom_up_adjust(index)
		parent = parent_index(index)
		return if parent < 0

		if @heap[parent] < @heap[index]
			@heap[parent], @heap[index] = @heap[index], @heap[parent]
			bottom_up_adjust(parent)
		end
	end

	def top_down_adjust(index)
		left  = left_child_index(index)
		right = right_child_index(index)

		return if @heap[left].nil? # 2分ヒープの性質より左の子がなければ右の子もない
		if @heap[index] < @heap[left]
			@heap[left], @heap[index] = @heap[index], @heap[left]
			top_down_adjust(left)
		end

		return if @heap[right].nil?
		if @heap[index] < @heap[right]
			@heap[right], @heap[index] = @heap[index], @heap[right]
			top_down_adjust(right)
		end
	end

	def parent_index(index)
		# 1オリジンで計算してから0オリジンに直す
		(index + 1) / 2 - 1
	end

	def left_child_index(index)
		index * 2 + 1
	end

	def right_child_index(index)
		index * 2 + 2
	end

end

queue = PriorityQueue.new
while (input = STDIN.gets.chomp!) != "end"
	cmd, param = input.split[0..1]
	if cmd == "insert"
		queue.insert(param.to_i)
	elsif cmd == "extract"
		puts queue.extract
	end
end