#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define REP(i, n) for(LL i = 0; i < (LL)(n); i++)
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()

template<typename T>
class SegmentTree {
private:
    LL N;
    vector<T> v;
    vector<tuple<LL, LL, T>> heap;
    function<T(T, T)> merge;

    T init(LL l, LL r, LL i) {
        if(l == r) {
            return 0;
        }
        if(r - l == 1) {
            T value = v[l];
            heap[i] = make_tuple(l, r, value);
            return value;
        }
        T value = merge(init(l, (l + r)/2, i*2), init((l + r)/2, r, i*2 + 1));
        heap[i] = make_tuple(l, r, value);
        return value;
    }

public:
    SegmentTree() {}

    SegmentTree(vector<T> s, function<T(T, T)> f) {
        merge = f;
        LL n = s.size();
        for(N = 1;N < n;N *= 2);
        heap.resize(2*N, make_tuple(0, 0, 0));
        v.resize(N, 0);
        copy(s.begin(), s.end(), v.begin());
        init(0, N, 1);
    }

    SegmentTree(vector<T> s) : SegmentTree(s, [](T x, T y){return x + y;}) {}

    void update(LL index, T value) {
        LL l = 0;
        LL r = N;
        LL i = 1;
        for(;1 < r - l;) {
            LL mid = (l + r)/2;
            if(index < mid) {
                r = mid;
                i *= 2;
            }else{
                l = mid;
                i = i*2 + 1;
            }
        }
        heap[i] = make_tuple(l, r, value);

        for(i /= 2;0 < i;i /= 2) {
            LL l = get<0>(heap[i]);
            LL r = get<1>(heap[i]);
            T v = merge(get<2>(heap[i*2]), get<2>(heap[i*2 + 1]));
            heap[i] = make_tuple(l, r, v);
        }
    }

    T segment(LL l, LL r, LL i=1) {
        LL left = get<0>(heap[i]);
        LL right = get<1>(heap[i]);
        LL mid = (left + right)/2;
        T value = get<2>(heap[i]);

        if(l == r) {
            return 0;
        }
        if(left == right) {
            return 0;
        }
        if(left == l && right == r) {
            return value;
        }
        if(r < mid) {
            return segment(l, r, i*2);
        }
        if(mid < l) {
            return segment(l, r, i*2 + 1);
        }
        return merge(segment(l, mid, i*2), segment(mid, r, i*2 + 1));
    }
};

bool check(LL N, vector<LL> a, LL p) {
    vector<LL> t(a);
    REP(i, N) {
        t[i] = p <= a[i] ? 1 : -1;
    }
    vector<LL> s(N + 1, 0);
    REP(i, N) {
        s[i + 1] = s[i] + t[i];
    }
    vector<LL> v(2*N + 1, 0);
    SegmentTree<LL> seg(v);
    LL ans = 0;
    REP(i, N + 1) {
        LL j = s[i] + N;
        ans += seg.segment(0, j + 1);
        LL y = seg.segment(j, j + 1);
        seg.update(j, y + 1);
    }
    return (N + 1)*N/4 <= ans;
}

int main() {
    LL N;
    cin >> N;
    vector<LL> a(N);
    REP(i, N) {
        cin >> a[i];
    }
    vector<LL> com(a);
    sort(ALL(com));

    LL left = 0;
    LL right = N - 1;
    if(check(N, a, com[right])) {
        cout << com[right] << endl;
        return 0;
    }

    for(;1 < right - left;) {
        int mid = (left + right)/2;
        bool c = check(N, a, com[mid]);
        if(c) {
            left = mid;
        }else{
            right = mid;
        }
    }
    cout << com[left] << endl;
    return 0;
}


Measured memory_bytes: 25228