#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i, sz(v)) { if (i) os << " "; os << v[i]; } return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a - mod; }

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
      solve();
    }
}


template<typename T>
class SegTree {
    int n;
    T def;
    function<T(T, T)> operation;
    function<T(T, T)> update;
    vector<T> data;

    T _query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return def;
        if (a <= l && r <= b) return data[k];
        T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2);
        T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r);
        return operation(c1, c2);
    }

public:
    SegTree<T>(int _n, T _def, function<T(T, T)> _operation, function<T(T, T)> _update)
    : def(_def), operation(_operation), update(_update) {
        n = 1;
        while (n < _n) n *= 2;
        data = vector<T>(2 * n - 1, def);
    }

    T query(int a, int b) {
        return _query(a, b, 0, 0, n);
    }

    void change(int i, T x) {
        i += n - 1;
        data[i] = update(data[i], x);
        while (i > 0) {
            i = (i - 1) / 2;
            data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    T operator[](int i) { return data[i + n - 1]; }
};

int n;
vector<ll> a;

bool check(int x) {
    vector<ll> acc(n + 1);
    rep3(i, 1, n + 1) if (a[i - 1] <= x) acc[i] = 1;
    // cout << endl << acc << endl;
    rep3(i, 1, n + 1) acc[i] = acc[i] + acc[i - 1];
    // cout << acc << endl;
    rep(i, n + 1) acc[i] = 2 * acc[i] - i;
    reverse(all(acc));
    // cout << x << endl << acc << endl;

    // 転倒数
    vector<pair<ll, int> > tmp(n + 1);
    rep(i, n + 1) tmp[i] = {acc[i], i};
    sort(all(tmp), greater<pair<ll, int> >());

    SegTree<ll> sgt(n + 1, 0, [](ll a, ll b) { return a + b; }, [](ll a, ll b) { return b; });
    ll sum = 0;
    rep(i, n + 1) {
      sum += sgt.query(0, tmp[i].S);
      sgt.change(tmp[i].S, 1);
    }
    if (sum > 1LL * n * (n + 1) / 4) return 1;

    return 0;
}

template<typename T>
void binary_search(T ok, T ng) {
    while (abs(ng - ok) > 1) {
        T mid = (ng + ok) / 2;
        (check(mid) ? ok : ng) = mid;
    }
    cout << ok << endl;
}
void solve() {
  cin >> n;
  a.resize(n);
  rep(i, n) cin >> a[i];
  binary_search(inf, 0);
}

/*
答えの中央値を ok とする
中央値が ok 以下である iff ok 以下の数が m / 2 個より真に多い
m : 今見ている部分列の要素数

ok を小さくする方が厳しい
ok が 1 以下の方が, ok が 5 以下より厳しい

求めるのは, ok 以下の数が m / 2 個より真に多い部分列の数

https://www.creativ.xyz/arc101-d-916/
*/


Measured memory_bytes: 7480