module BIT = struct
  let create n v = (n, Array.make (n+1) v)
  let add idx v (l, a) =
    let rec f i =
      if i <= l then begin
        a.(i) <- a.(i) + v;
        f (i + i land (-i))
      end
    in f idx
  let query idx (_, a) = let rec f i v =
      if i = 0 then v
      else f (i - i land (-i)) (v + a.(i))
    in f idx 0
end

let rec upper_bound l r p =
  if l+1 >= r then l else
  let m = (l+r) / 2 in
  if p m then upper_bound m r p else upper_bound l m p

let () =
  Scanf.scanf "%d" @@ fun n ->
  let a = Array.init n (fun _ -> Scanf.scanf " %d" ((+) 0)) in
  let b = Array.init n (fun i -> a.(i)) in
  Array.sort (-) b;
  upper_bound 0 n (fun idx ->
    let v = b.(idx) in
    let c = Array.init (n+1) (fun i ->
      if i = 0 then 0
      else if a.(i-1) >= v then 1 else -1) in
    for i = 1 to n do c.(i) <- c.(i) + c.(i-1) done;

    let bit = BIT.create (2*n+2) 0 in
    let ofs = n+1 in

    let x =
      Array.fold_left (fun s v ->
        let s = s + BIT.query (v+ofs) bit in
        BIT.add (v+ofs) 1 bit; s
      ) 0 c
    in x >= n * (n+1) / 2 / 2
  ) |> fun idx -> Printf.printf "%d\n" b.(idx)