#[allow(unused_imports)]
use std::cmp::{min,max};
#[allow(unused_imports)]
use std::collections::{BTreeMap,BTreeSet};
#[allow(unused_imports)]
use std::ops::*;
#[allow(unused_imports)]
use std::collections::BinaryHeap;

#[allow(unused_macros)]
macro_rules! tf {
    ($c:expr, $t:expr, $f:expr) => {{
        if $c { $t } else { $f }
    }};
}

struct BIT<T> {
    xs: Vec<T>,
    n: usize,
}

// 0-indexed
impl<T:Add<T,Output=T>+Sub<T,Output=T>+Default+Clone+Copy> BIT<T> {
    fn new(n: usize) -> BIT<T> {
        let mut m = 1;
        while m <= n {
            m *= 2;
        }
        let n = m;
        BIT::<T> {
            xs: vec![T::default(); n+1],
            n: n
        }
    }
    fn sum(&self, i: usize) -> T {
        let mut i = i + 1;
        let mut res = T::default();
        while i > 0 {
            res = res + self.xs[i];
            i = i - (1usize << i.trailing_zeros());
        }
        res
    }
    fn range_sum(&self, l: usize, r: usize) -> T {
        if l < r {
            self.sum(r) - self.sum(l)
        }
        else {
            T::default()
        }
    }
    fn add(&mut self, i: usize, x: T) {
        let mut i = i + 1;
        while i <= self.n {
            self.xs[i] = self.xs[i] + x;
            i = i + (1usize << i.trailing_zeros())
        }
    }
}

fn compression<T:Ord+Copy>(xs: &Vec<T>) -> BTreeMap<T, usize> {
    let mut res: BTreeMap<T, usize> = BTreeMap::new();
    let mut ys = xs.clone();
    ys.sort();
    for i in 0..ys.len() {
        if i == 0 || ys[i-1] != ys[i] {
            let k = res.len();
            res.insert(ys[i], k);
        }
    }
    res
}

fn inversions<T:Copy+Ord>(xs: &Vec<T>) -> usize {
    let n = xs.len();
    let map = compression(&xs);
    let mut bit: BIT<usize> = BIT::new(n);
    let mut res = 0;
    for i in 0..n {
        res += bit.range_sum(map[&xs[i]], n);
        bit.add(map[&xs[i]], 1);
    }
    res
}

fn cumsum<T:Default+Add<T,Output=T>+Clone+Copy>(xs: &Vec<T>) -> Vec<T> {
    let n = xs.len();
    let mut res = vec![T::default(); n+1];
    for i in 0..n {
        res[i+1] = res[i] + xs[i];
    }
    res
}

fn main() {
    let n = read_i64() as usize;
    let xs = read_vec_i64();
    let mut lower = 0;
    let mut upper = 1i64 << 32;
    while upper - lower != 1 {
        //eprintln!("{}~{}", lower, upper);
        //read_line();
        let m = (upper + lower) / 2;
        let ys: Vec<i64> = xs.iter().map(|&x| tf!(x>=m, 1, -1)).collect();
        let zs = cumsum(&ys);
        let inv = inversions(&zs);
        //eprintln!("inv = {}", inv);
        let judge = (n+1) * (n) / 2 <= 2 * ((n+1) * (n) / 2 - inv);
        if judge {
            lower = m;
        }
        else {
            upper = m;
        }
    }
    println!("{}", lower);
}

#[allow(dead_code)]
fn read_line() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    ret.pop();
    //ret.pop();
    return ret;
}

#[allow(dead_code)]
fn read_i64() -> i64 {
    let ss = read_line();
    return ss.parse::<i64>().unwrap();
}

#[allow(dead_code)]
fn read_vec_i64() -> Vec<i64> {
    let mut res = vec![];
    let ss = read_line();
    for ts in ss.split_whitespace() {
        let x = ts.parse::<i64>().unwrap();
        res.push(x);
    }
    return res;
}

use std::fmt::Display;
#[allow(dead_code)]
fn write_vec<T: Display>(xs: &Vec<T>) {
    if xs.len() == 0 {
        println!("");
        return;
    }
    print!("{}", xs[0]);
    for i in 1..xs.len() {
        print!(" {}", xs[i]);
    }
    println!("");
}


Measured memory_bytes: 12540