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: # encoding: utf-8
  N = int(input())
  a = list(map(int, input().split()))
  
  dict_count = {}
  seq_list = []
  # count num of submeds
  for i, ai in enumerate(a):
      # existing sequences
      for seq in seq_list:
          seq_temp = list(seq)
          for k in range(len(seq)):
              if ai <= seq[k]:
                  seq_temp.insert(k, ai)
                  break
          else:
              seq_temp.insert(-1, ai)
          # update dict
          submed = seq_temp[len(seq_temp) // 2]
          if submed in dict_count.keys():
              dict_count[str(submed)] += 1
          else:
              dict_count[str(submed)] = 1
      # new sequence [ai]
      seq_list.append([ai])
      if ai in dict_count.keys():
          dict_count[str(ai)] += 1
      else:
          dict_count[str(ai)] = 1
  
  # ans
  keys = sorted(dict_count.keys())
  med = sum(dict_count.values()) // 2
  med_temp = 0
  for key in keys:
      med_temp += dict_count[key]
      if med_temp >= med:
          print(key)
          break
  
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"}]