output_description: For each "extract" operation, print the element extracted from the priority
  queue $S$ in a line.
input_description: Multiple operations to the priority queue $S$ are given. Each operation is
  given by "insert $k$", "extract" or "end" in a line. Here, $k$ represents an
  integer element to be inserted to the priority queue.
  
  The input ends with "end" operation.
attempt: def setHeapDown_max(heap, pos):
      targetkey = heap[pos]
      while pos > 0:
          parentpos = (pos - 1) >> 1
          parent = heap[parentpos]
          if parent < targetkey:
              heap[pos] = parent
              pos = parentpos
              continue
          break
      heap[pos] = targetkey
  
  
  def setHeapUp_max(heap, pos):
      endpos = len(heap)
      targetkey = heap[pos]
      childpos = 2 * pos + 1
      while childpos < endpos:
          rightpos = childpos + 1
          if rightpos < endpos and not heap[rightpos] < heap[childpos]:
              childpos = rightpos
          heap[pos] = heap[childpos]
          pos = childpos
          childpos = 2 * pos + 1
      heap[pos] = targetkey
      setHeapDown_max(heap, pos)
  
  
  def heapPush_max(heap, key):
      heap.append(key)
      setHeapDown_max(heap, len(heap) - 1)
  
  
  def heapPop_max(heap):
      lastkey = heap.pop()
      if heap:
          returnkey = heap[0]
          heap[0] = lastkey
          setHeapUp_max(heap, 0)
          return returnkey
      return lastkey
  
  
  import sys
  
  S = []
  
  ans = []
  
  for x in sys.stdin.readlines():
      if x[0] == "i":
          k = int(x[7:])
          heapPush_max(S, k)
      elif x[1] == "x":
          ans.append(heapPop_max(S))
      else:
          pass
  
  print(*ans, sep="\n")
  
problem_description: Priority Queue
  
  A priority queue is a data structure which maintains a set $S$ of elements,
  each of with an associated value (key), and supports the following operations:
  
    * $insert(S, k)$: insert an element $k$ into the set $S$
    * $extractMax(S)$: remove and return the element of $S$ with the largest key
  
  Write a program which performs the $insert(S, k)$ and $extractMax(S)$
  operations to a priority queue $S$. The priority queue manages a set of
  integers, which are also keys for the priority.
samples: [{"input": "insert 8\n    insert 2\n    extract\n    insert 10\n    extract\n    insert 11\n    extract\n    extract\n    end", "output": "8\n    10\n    11\n    2"}]