local mfl, mce, mmi = math.floor, math.ceil, math.min
local mma = math.max
local SegTree = {}
SegTree.updateAll = function(self)
  for i = self.stagenum - 1, 1, -1 do
    for j = 1, self.cnt[i] do
      self.stage[i][j] = self.stage[i + 1][j * 2 - 1] + self.stage[i + 1][j * 2]
    end
  end
end
SegTree.clear = function(self)
  for i = self.stagenum, 1, -1 do
    for j = 1, self.cnt[i] do
      self.stage[i][j] = 0
    end
  end
end
SegTree.create = function(self, n)
  local stagenum, mul = 1, 1
  self.cnt, self.stage, self.size = {1}, {{}}, {}
  while mul < n do
    mul, stagenum = mul * 2, stagenum + 1
    self.cnt[stagenum], self.stage[stagenum] = mul, {}
  end
  for i = 1, stagenum do self.size[i] = self.cnt[stagenum + 1 - i] end
  self.stagenum = stagenum
  self:clear()
end
SegTree.getRange = function(self, right)
  local stage = 1
  while right < self.size[stage] do
    stage = stage + 1
  end
  local ret = 0
  local l, r = 1, right
  while true do
    local sz = self.size[stage]
    ret = ret + self.stage[stage][mce(l / sz)]
    l = l + sz
    if l <= r then
      local nsize = r + 1 - l
      while nsize < self.size[stage] do
        stage = stage + 1
      end
    else
      break
    end
  end
  return ret
end
SegTree.inc = function(self, idx)
  self.stage[self.stagenum][idx] = self.stage[self.stagenum][idx] + 1
end
SegTree.dec = function(self, idx)
  self.stage[self.stagenum][idx] = self.stage[self.stagenum][idx] - 1
  for i = self.stagenum - 1, 1, -1 do
    local dst = mce(idx / 2)
    local rem = dst * 4 - 1 - idx
    self.stage[i][dst] = self.stage[i + 1][idx] + self.stage[i + 1][rem]
    idx = dst
  end
end
SegTree.new = function(n)
  local obj = {}
  setmetatable(obj, {__index = SegTree})
  obj:create(n)
  return obj
end

local n = io.read("*n")
local a = {}
local t = {}
for i = 1, n do
  a[i] = io.read("*n")
  t[i] = a[i]
end
table.sort(t)
local totcnt = mfl(n * (n + 1) / 2)
local st = SegTree.new(n * 2 + 1)
local z = {}
local function solve(v)
  st:clear()
  local ofst = n + 1
  z[1] = v <= a[1] and 1 or -1
  for i = 2, n do
    z[i] = v <= a[i] and z[i - 1] + 1 or z[i - 1] - 1
  end
  for i = 1, n do
    st:inc(z[i] + ofst)
  end
  st:updateAll()
  local cnt = 0
  local n2_1 = 2 * n + 1
  for i = 1, n do
    local left = i == 1 and ofst or z[i - 1] + ofst
    if left <= 1 then
      cnt = cnt + n + 1 - i
    else
      cnt = cnt + n + 1 - i - st:getRange(left - 1)
    end
    st:dec(z[i] + ofst)
  end
  return totcnt <= cnt * 2
end
local function solveAll()
  if solve(t[n]) then
    return t[n]
  end
  local min, max = 1, n
  while 1 < max - min do
    local mid = mfl((min + max) / 2)
    if solve(t[mid]) then
      min = mid
    else
      max = mid
    end
  end
  return t[min]
end
print(solveAll())
