//
//  na 2380.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/14.
//

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
typedef long long int ll;
const int maxn = 3e5 + 5;
int n, a[maxn], vs[maxn], vl;
struct Tree{
#define lowbit(x) (x & -x)
static const int lim = maxn * 2;
int val[lim];
inline void insert(int pos, int dv){
    for(; pos < lim; pos += lowbit(pos))
        val[pos] += dv;
}
inline int query(int lim){
    int res = 0;
    for(; lim; lim -= lowbit(lim))
        res += val[lim];
    return res;
}
#undef lowbit
inline void clear(){
    memset(val, 0, sizeof(val));
}
}tree;
inline ll check(int lim){
//    cerr << "check " << lim << endl;
    ll res = 0;
    tree.clear();
    int base = n + 1;
    tree.insert(base, 1);
    for(int i = 0; i < n; ++i){
        base += a[i] >= lim? 1: -1;
        res += tree.query(base - 1);
        tree.insert(base, 1);
    }
//    cerr << "res: " << res << " intervals" << endl;
    return res;
}
#define READFILE
int main(){
#if    defined(MAC_OS_VERSION_11_0) && defined(READFILE)
    freopen("/Users/m2/Downloads/problem_2380/ex_median2.in", "r", stdin);
#endif
    cin.tie(0)->sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        vs[i] = a[i];
    }
    sort(vs, vs + n);
    vl = int(unique(vs, vs + n) - vs);
    for(int i = 0; i < n; ++i)
        a[i] = int(lower_bound(vs, vs + vl, a[i]) - vs);
//    cerr << "a = { ";
//    for(int i = 0; i < n; ++i)
//        cerr << a[i] << ' ';
//    cerr << "}" << endl;
    int lt = 0, rt = vl, mid;
    ll rank = ((ll(n + 1) * n / 2) + 1) / 2;
    while(lt < rt - 1){
        mid = (lt + rt) >> 1;
        if(check(mid) >= rank)
            lt = mid;
        else
            rt = mid;
    }
    cout << vs[lt] << endl;
    return 0;
}