use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn calc(seq: &Vec<i64>, v: i64) -> usize {
    let n = seq.len();
    let mut total_cnts = vec![0, 0];
    let mut cnts = vec![vec![]; 2];
    let mut ret = 0;
    for i in 0..n {
        if seq[i] < v {
            let cnt1;
            if let Some(c) = cnts[1].pop() {
                total_cnts[1] -= c;
                cnt1 = 1 + c;
            } else {
                cnt1 = 1;
            }
            total_cnts[0] += cnt1;
            cnts[0].push(cnt1);
        } else {
            let cnt0;
            if let Some(c) = cnts[0].pop() {
                total_cnts[0] -= c;
                cnt0 = c;
            } else {
                cnt0 = 0;
            }
            if cnts[1].len() == 0 {
                cnts[1].push(1);
            } else {
                let l = cnts[1].len();
                cnts[1][l - 1] += 1;
            }
            total_cnts[1] += 1 + cnt0;
            cnts[1].push(cnt0);
        }
        // println!("{:?}", total_cnts);
        // println!("^ {:?}", cnts[1]);
        // println!("v {:?}", cnts[0]);
        ret += total_cnts[1];
    }
    return ret;
}

fn main() {
    let n = read::<usize>();
    let mut seq = vec![0; n];
    for i in 0..n {
        seq[i] = read::<i64>();
    }
    let ans = solve(&seq);
    println!("{}", ans);
    // let ans2 = naive(&seq);
}

fn solve(seq: &Vec<i64>) -> i64 {
    let n = seq.len();
    let m = n * (n + 1) / 2;
    let mut sort_seq = seq.clone();
    sort_seq.sort();
    let mut l = 0;
    let mut r = n;
    while r - l > 1 {
        let index = (r + l) / 2;
        let v = sort_seq[index];
        let target = if m % 2 == 0 { m / 2 } else { m / 2 + 1 };
        if calc(seq, v) >= target {
            l = index;
        } else {
            r = index;
        }
    }
    return sort_seq[l];
}

fn naive(seq: &Vec<i64>) -> i64 {
    let n = seq.len();
    let mut meds = vec![];
    for l in 0..n {
        for r in l..n {
            let mut items = vec![];
            for i in l..(r + 1) {
                items.push(seq[i]);
            }
            items.sort();
            meds.push(items[items.len() / 2]);
        }
    }
    meds.sort();
    // println!("{:?}", meds);
    return meds[meds.len() / 2];
}

#[allow(dead_code)]
struct XorShift {
    x: u32,
    y: u32,
    z: u32,
    w: u32,
}
#[allow(dead_code)]
impl XorShift {
    fn new() -> XorShift {
        XorShift {
            x: 0x34fb2383,
            y: 0x327328fa,
            z: 0xabd4b54a,
            w: 0xa9dba8d1,
        }
    }
    fn seed(s: u32) -> XorShift {
        let mut rnd = XorShift::new();
        rnd.w = s;
        rnd
    }
    fn xor128(&mut self) -> u32 {
        let t = self.x ^ (self.x << 11);
        self.x = self.y;
        self.y = self.z;
        self.z = self.w;
        self.w = (self.w ^ (self.w >> 19)) ^ (t ^ (t >> 8));
        self.w
    }
    fn next_i32(&mut self, r: i32) -> i32 {
        (self.xor128() % r as u32) as i32
    }
    fn next_i32_lr(&mut self, l: i32, r: i32) -> i32 {
        self.next_i32(r - l + 1) + l
    }
    fn next_i64(&mut self, r: i64) -> i64 {
        ((((self.xor128() as u64) << 32) + self.xor128() as u64) % r as u64) as i64
    }
    fn next_i64_lr(&mut self, l: i64, r: i64) -> i64 {
        self.next_i64(r - l + 1) + l
    }
    fn next_f64(&mut self, r: f64) -> f64 {
        (self.xor128() as f64) / (0xffffffffu32 as f64) * r
    }
    fn next_f64_lr(&mut self, l: f64, r: f64) -> f64 {
        self.next_f64(r - l) + l
    }
}

#[test]
fn test() {
    let mut rnd = XorShift::new();
    for _iter in 0..100 {
        let n = rnd.next_i32_lr(1, 8) as usize;
        let mut seq = vec![0; n];
        for i in 0..n {
            seq[i] = rnd.next_i64_lr(1, 10);
        }
        let v1 = solve(&seq);
        let v2 = naive(&seq);
        if v1 != v2 {
            println!("{}", n);
            for i in 0..n {
                print!("{} ", seq[i]);
            }
            println!("");
            println!("solve={} naive={}", v1, v2);
            assert!(v1 == v2);
        }
    }
}


Measured memory_bytes: 8444