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
  from operator import itemgetter
  
  input = sys.stdin.readline
  
  
  def compress(lis, n=2, last_sort=False):
      length = len(lis)
      first_value = -1
      for i in range(n):
          lis.sort(key=itemgetter(i))
          value = first_value
          index = 0
          for j in range(length):
              if lis[j][i] != value:
                  index += 1
              value = lis[j][i]
              lis[j][i] = index
  
      if last_sort:
          lis.sort()
      return lis
  
  
  class BIT:
      def __init__(self, n):
          self.n = n
          self.bit = [0] * (n + 1)
          self.value = [0] * (n + 1)
  
      def sum(self, i):
          s = 0
          while i > 0:
              s += self.bit[i]
              i -= i & -i
          return s
  
      def add(self, i, x):
          # assert i > 0
          self.value[i] += x
          while i <= self.n:
              self.bit[i] += x
              i += i & -i
  
      def subtract(self, i, x):
          self.add(i, -x)
  
      def init(self, n, lis):
          self.n = n
          self.bit = [0] * (n + 1)
          self.value = lis
          for i in range(n):
              self.add(i, lis[i])
  
      def get_value(self, i):
          return self.value[i]
  
      def get_sum(self, i, j):
          return self.sum(j) - self.sum(i)
  
      def lower_bound(self, x):  # 和がx以上になる最小のインデックス
          if x <= 0:
              return 0
          l, r = 0, self.n
          while r - l > 1:
              index = (r + l) // 2
              if self.sum(index) >= x:
                  r = index
              else:
                  l = index
  
          if self.sum(l) >= x:
              return l
          return r
  
      def upper_bound(self, x):  # 和がx以下になる最大のインデックス
          if x <= 0:
              return 0
          l, r = 0, self.n
          while r - l > 1:
              index = (r + l) // 2
              if self.sum(index) <= x:
                  l = index
              else:
                  r = index
  
          if self.sum(r) <= x:
              return r
          return l
  
      def reset(self):
          self.bit = [0] * (self.n + 1)
          self.value = [0] * (self.n + 1)
  
  
  def main():
      n = int(input())
      b = list(map(int, input().split()))
      a = [[int(i), int(x)] for i, x in enumerate(b)]
  
      compress(a)
      key_list = dict()
      for i, x in a:
          key_list[x] = b[i - 1]
      a = [x[1] for x in a]
  
      l, r = 0, max(a)
      bit = BIT(n + 3)
      border = (n + 1) * n // 4 + 1
  
      while r - l > 1:
          k = (l + r) // 2
  
          s = [0] * (n + 1)
          for i in range(n):
              if a[i] >= k:
                  s[i + 1] += 1
              else:
                  s[i + 1] -= 1
              s[i + 1] += s[i]
          floor = min(s)
          for i in range(n + 1):
              s[i] -= floor - 1
  
          count = 0
          bit.reset()
          for i in range(n + 1):
              count += bit.sum(s[i])
              bit.add(s[i] + 1, 1)
  
          if count >= border:
              l = k
          else:
              r = k
  
      print(key_list[r])
  
  
  if __name__ == "__main__":
      main()
  
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"}]