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())
  a = list(map(int, input().split(" ")))
  b = sorted(a)
  m = b[N // 2]
  lst = []
  
  dic = {}
  
  
  def dfs(l, r, mid):
      dic[(l, r)] = 1
      lst.append(mid)
  
      if l == r:
          return
  
      if (r - l + 1) % 2 == 0:
          if a[r] < mid:
              if not (l, r - 1) in dic:
                  dfs(l, r - 1, mid)
          else:
              if not (l, r - 1) in dic:
                  c = sorted(a[l:r])
                  mid_ = c[(len(c) // 2)]
                  dfs(l, r - 1, mid_)
  
          if a[l] < mid:
              if not (l + 1, r) in dic:
                  dfs(l + 1, r, mid)
  
          elif not (l + 1, r) in dic:
              c = sorted(a[l + 1 : r + 1])
              mid_ = c[(len(c) // 2)]
              dfs(l + 1, r, mid_)
      else:
          if a[r] > mid:
              if not (l, r - 1) in dic:
                  dfs(l, r - 1, mid)
          else:
              if not (l, r - 1) in dic:
                  c = sorted(a[l:r])
                  mid_ = c[len(c) // 2]
                  dfs(l, r - 1, mid_)
  
          if a[l] > mid:
              if not (l + 1, r) in dic:
                  dfs(l + 1, r, mid)
  
          else:
              if not (l + 1, r) in dic:
                  c = sorted(a[l + 1 : r + 1])
                  mid_ = c[(len(c) // 2)]
                  dfs(l + 1, r, mid_)
  
  
  dfs(0, N - 1, m)
  lst.sort()
  l = len(lst)
  print(lst[(l // 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"}]