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: n = int(input())
  lst = list(map(int, input().split()))
  ans = []
  for i in range(1, n + 1):
      for e in range(0, n + 1 - i):
          ans.append(sorted(lst[e : e + i])[i // 2])
  print(ans)
  print(sorted(ans)[len(ans) // 2])
  
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"}]