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: from itertools import accumulate
  
  N = int(input())
  As = list(map(int, input().split()))
  
  Bs = sorted(As)
  M = N * (N + 1) // 2
  
  
  def isOK(mid):
      Am = Bs[mid]
      Ss = [1 if A >= Am else -1 for A in As]
      Ss = list(accumulate([0] + Ss))
  
      def makeBIT(numEle):
          numPow2 = 2 ** (numEle - 1).bit_length()
          data = [0] * (numPow2 + 1)
          return data, numPow2
  
      def addValue(iA, A):
          iB = iA + 1
          while iB <= numPow2:
              data[iB] += A
              iB += iB & -iB
  
      def getSum(iA):
          iB = iA + 1
          ans = 0
          while iB > 0:
              ans += data[iB]
              iB -= iB & -iB
          return ans
  
      data, numPow2 = makeBIT(N + 1)
      iSs = list(range(N + 1))
      iSs.sort(key=lambda iS: Ss[iS])
      odrSs = [0] * (N + 1)
      for odrS, iS in enumerate(iSs):
          odrSs[iS] = odrS
  
      num = 0
      for odrS in odrSs:
          num += getSum(odrS)
          addValue(odrS, 1)
      return num >= (M + 1) // 2
  
  
  ng, ok = N, -1
  while abs(ok - ng) > 1:
      mid = (ng + ok) // 2
      if isOK(mid):
          ok = mid
      else:
          ng = mid
  
  print(Bs[ok])
  
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"}]