//
// main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <complex>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;
constexpr ll LL_MAX = numeric_limits<ll>::max();
constexpr ull ULL_MAX = numeric_limits<ull>::max();

template<typename T>
vector<T> make_vec_nd(T init, ll size) {
    return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, ll size, Args... rest) {
    auto inner = make_vec_nd(init, rest...);
    return vector<decltype(inner)>(size, inner);
}

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrep(i, a, b) for (ll i = (a)-1; i >= (b); i--)

template<typename Monoid>
struct SegmentTree {
    using Op = function<Monoid(const Monoid& lhs, const Monoid& rhs)>;
    ll width;
    vector<Monoid> node;
    Op op;
    Monoid unit;
    
    SegmentTree(ll N, Op op, Monoid unit)
    : SegmentTree(vector<Monoid>(N, unit), op, unit) {}
    SegmentTree(const vector<Monoid>& elems, Op op, Monoid unit)
    : op(op)
    , unit(unit) {
        width = 1;
        while (width < elems.size()) {
            width *= 2;
        }
        node.resize(2 * width - 1, unit);
        for (size_t i = 0; i < elems.size(); i++) {
            node[i + width - 1] = elems[i];
        }
        for (size_t i = width - 2; i != numeric_limits<size_t>::max(); i--) {
            node[i] = op(node[2 * i + 1], node[2 * i + 2]);
        }
    }
    void update(ll idx, Monoid elem) {
        idx += width - 1;
        node[idx] = elem;
        while (idx >= 1) {
            idx = (idx - 1) / 2;
            node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
        }
    }
    Monoid query_core(ll a, ll b, ll root, ll left, ll right) const {
        assert(0 <= a && b <= width);
        if (right <= a || b <= left) {
            return unit;
        }
        if (a <= left && right <= b) {
            return node[root];
        }
        ll mid = (left + right) / 2;
        Monoid ans_l = query_core(a, b, 2 * root + 1, left, mid);
        Monoid ans_r = query_core(a, b, 2 * root + 2, mid, right);
        return op(ans_l, ans_r);
    }
    Monoid query(ll a, ll b) const {
        assert(0 <= a && b <= width);
        return query_core(a, b, 0, 0, width);
    }
    Monoid operator[](size_t idx) { return query(idx, idx + 1); }
};

int main() {
    ll N;
    cin >> N;
    vector<ll> As(N);
    rep(i,0,N) {
        cin >> As[i];
    }
    
//    ll N = 100000;
//    vector<ll> As(N);
//    rep(i,0,N) {
//        As[i] = random() % 1000000000 + 1;
//    }
    
//    clock_t start = clock();
    
    ll left = 0;
    ll right = *max_element(As.begin(), As.end());
    auto count_median_leq = [N, &As](ll k){
//        clock_t start = clock();
        
        struct SumVal {
            ll idx;
            ll sum;
        };
        vector<SumVal> sums(N+1);
        rep(n,1,N+1) {
            sums[n].idx = n;
            sums[n].sum = sums[n-1].sum;
            if (As[n-1] <= k) {
                sums[n].sum++;
            } else {
                sums[n].sum--;
            }
        }
        
//        clock_t lap0 = clock();
        
        sort(sums.begin(), sums.end(), [](SumVal& lhs, SumVal& rhs){
            return lhs.sum < rhs.sum || (lhs.sum == rhs.sum && lhs.idx > rhs.idx);
        });
        
//        clock_t lap1 = clock();
        
        SegmentTree<ll> tree(vector<ll>(N+1), [](ll lhs, ll rhs){
            return lhs + rhs;
        }, 0);
        
//        clock_t lap2 = clock();
        
        ll cnt = 0;
        rrep(i,N+1,0) {
            cnt += tree.query(sums[i].idx, N+1);
            tree.update(sums[i].idx, 1);
        }
        
//        clock_t lap3 = clock();
//        const double time0 = static_cast<double>(lap0 - start) / CLOCKS_PER_SEC;
//        const double time1 = static_cast<double>(lap1 - lap0) / CLOCKS_PER_SEC;
//        const double time2 = static_cast<double>(lap2 - lap1) / CLOCKS_PER_SEC;
//        const double time3 = static_cast<double>(lap3 - lap2) / CLOCKS_PER_SEC;
//        cout << "time0: " << time0 << endl;
//        cout << "time1: " << time1 << endl;
//        cout << "time2: " << time2 << endl;
//        cout << "time3: " << time3 << endl;
        
//        cout << "count_median_leq: " << time << endl;
        return cnt;
    };
    ll range_cnt = (N * (N+1)) / 2;
    while (right - left >= 2) {
        ll mid = (left + right) / 2;
        ll cnt = count_median_leq(mid);
        if (cnt >= range_cnt / 2 + 1) {
            right = mid;
        } else {
            left = mid;
        }
    }
    cout << right << endl;
    
//    clock_t end = clock();
    
//    const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC;
//    cout << "total: " << time << endl;
}



Measured memory_bytes: 7464