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: import sys
  
  
  class priority_queue:
      def __init__(self, MAX_SIZE):
          self.array = [0] * MAX_SIZE
          self.size = 0
  
      def len(self):
          return self.size
  
      def empty(self):
          return self.size == 0
  
      def push(self, data):
          self.array[self.size] = data
          index = self.size
          while index != 0 and self.array[index] > self.array[(index - 1) // 2]:
              self.array[index], self.array[(index - 1) // 2] = (
                  self.array[(index - 1) // 2],
                  self.array[index],
              )
              index = (index - 1) // 2
          self.size += 1
  
      def top(self):
          return self.array[0]
  
      def pop(self):
          self.size -= 1
          self.array[0], self.array[self.size] = self.array[self.size], self.array[0]
          index = 0
          while 2 * index + 1 < self.size:
              if 2 * index + 2 < self.size:
                  if (
                      self.array[2 * index + 2] > self.array[index]
                      and self.array[2 * index + 2] >= self.array[2 * index + 1]
                  ):
                      self.array[2 * index + 2], self.array[index] = (
                          self.array[index],
                          self.array[2 * index + 2],
                      )
                      index = 2 * index + 2
                  elif (
                      self.array[2 * index + 1] > self.array[index]
                      and self.array[2 * index + 1] >= self.array[index + 2]
                  ):
                      self.array[2 * index + 1], self.array[index] = (
                          self.array[index],
                          self.array[2 * index + 1],
                      )
                      index = 2 * index + 1
                  else:
                      break
              else:
                  if self.array[2 * index + 1] > self.array[index]:
                      self.array[2 * index + 1], self.array[index] = (
                          self.array[index],
                          self.array[2 * index + 1],
                      )
                      index = 2 * index + 1
                  else:
                      break
  
  
  if __name__ == "__main__":
      que = priority_queue(2000000)
      while True:
          s = sys.stdin.readline().split()
          if s[0] == "insert":
              que.push(int(s[1]))
          elif s[0] == "extract":
              sys.stdout.writelines("%d\n" % que.top())
              que.pop()
          else:
              break
  
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"}]