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 itertools
  
  N = int(input())
  A = [int(_) for _ in input().split()]
  
  
  def check(x):
      class SegmentTree:
          """
          Parameters
          ----------
          array : list
              to construct segment tree from
          f : func
              binary operation of the monoid
          e :
              identity element of the monoid
          size : int
              limit for array size
          """
  
          def __init__(self, array, f, e, size):
              self.f = f
              self.e = e
              self.size = size
              self.n = n = len(array)
              self.dat = [e] * n + array + [e] * (2 * size - 2 * n)
              self.build()
  
          def build(self):
              dat, n, f = self.dat, self.n, self.f
              for i in range(n - 1, 0, -1):
                  dat[i] = f(dat[i << 1], dat[i << 1 | 1])
  
          def modify(self, p, v):
              """
              set value at position p (0-indexed)
              """
              f, n, dat = self.f, self.n, self.dat
              p += n
              dat[p] = v
              while p > 1:
                  dat[p >> 1] = f(dat[p], dat[p ^ 1])
                  p >>= 1
  
          def query(self, l, r):
              """
              result on interval [l, r) (0-indexed)
              """
              f, e, n, dat = self.f, self.e, self.n, self.dat
              res = e
              l += n
              r += n
              while l < r:
                  if l & 1:
                      res = f(res, dat[l])
                      l += 1
                  if r & 1:
                      r -= 1
                      res = f(res, dat[r])
                  l >>= 1
                  r >>= 1
              return res
  
      cumsum = list(itertools.accumulate([0] + [1 if a <= x else -1 for a in A]))
      # sum([l:r)) = cumsum[r] - cumsum[l] >= 0
      # ⇔ cumsum[l] <= cumsum[r]
      e = 0
      size = 2 * N + 10
      ST = SegmentTree([e] * size, f=lambda x, y: x + y, e=e, size=size)
      count = 0
      for c in cumsum:
          c += N + 5
          count += ST.query(0, c + 1)
          ST.modify(c + 1, ST.query(c + 1, c + 2) + 1)
      return 2 * count > N * (N + 1) // 2
  
  
  A_sorted = [0] + sorted(set(A)) + [10**10]
  lb = 0
  rb = len(A_sorted) - 1
  # check(x) == Trueとなる最小のx
  while rb - lb > 1:
      mid = (rb + lb) // 2
      if check(A_sorted[mid]):
          rb = mid
      else:
          lb = mid
  print(A_sorted[rb])
  
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"}]