output_description: Print the median of m.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      a_1 a_2 ... a_N
attempt: import sys
  
  
  def select(A, i):  # A is a list, i is the ith element in that ordered list
      # NOTE all elements must be unique
      T = list(A)
      if len(A) <= 5:  # Base case, just find ith element
          T = list(A)
          T.sort()
          return T[i]
      p = median_of_medians(A)
      (A_l, A_r, i_p) = partition(A, p)
      if i_p == i:
          return p
      elif i_p < i:
          return select(A_r, i - i_p - 1)
      else:  # i_p > i
          return select(A_l, i)
  
  
  def median_of_medians(A):
      B = list()  # B will hold medians of sublists
      itrs, i = len(A) // 5, 0
      for j in range(itrs):  # divide list into sublists of len 5
          sub_list = A[i : i + 5]
          m = median(sub_list)
          B.append(m)
          i += 5
      end = len(A) % 5
      if end != 0:
          B.append(median(A[-end:]))  # add the last group to the pot
      p = select(B, len(B) // 2)
      return p
  
  
  def partition(A, p):  # splits the list into left and right half where
      # everything less is in the left list
      (A_l, A_r, i_p) = [], [], 0
      for elem in A:
          if p > elem:
              A_l.append(elem)
          elif p < elem:
              A_r.append(elem)
      i_p = len(A_l)
      return A_l, A_r, i_p
  
  
  def median(A):  # A cheat to find the median in our base case
      T = list(A)  # copies list!
      T.sort()
      i = len(T) / 2  #  in list of 4 selects the 3rd element
      return T[int(i)]
  
  
  n = int(input())
  a = list(map(int, sys.stdin.readline().split()))
  pivot = median_of_medians(a)
  print(pivot)
  
problem_description: Statement
  
  We will define the **median** of a sequence b of length M, as follows:
  
    * Let b' be the sequence obtained by sorting b in non-decreasing order. Then, the value of the (M / 2 + 1)-th element of b' is the median of b. Here, / is integer division, rounding down.
  
  For example, the median of (10, 30, 20) is 20; the median of (10, 30, 20, 40)
  is 30; the median of (10, 10, 10, 20, 30) is 10.
  
  Snuke comes up with the following problem.
  
  You are given a sequence a of length N. For each pair (l, r) (1 \leq l \leq r
  \leq N), let m_{l, r} be the median of the contiguous subsequence (a_l, a_{l +
  1}, ..., a_r) of a. We will list m_{l, r} for all pairs (l, r) to create a new
  sequence m. Find the median of m.
samples: [{"input": "3\n    10 30 20", "output": "30\n    \n\nThe median of each contiguous subsequence of a is as follows:\n\n  * The median of (10) is 10.\n  * The median of (30) is 30.\n  * The median of (20) is 20.\n  * The median of (10, 30) is 30.\n  * The median of (30, 20) is 30.\n  * The median of (10, 30, 20) is 20.\n\nThus, m = (10, 30, 20, 30, 30, 20) and the median of m is 30.\n\n* * *"}, {"input": "1\n    10", "output": "10\n    \n\n* * *"}, {"input": "10\n    5 9 5 9 8 9 3 5 4 3", "output": "8"}]