/*Bismillahir Rahmanir Rahim*///{
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long; using ld = long double;
const ll llinf = (1ll<<61)-1;
const double eps = 1e-6, ldeps = 1e-9;
struct Dbg {
static constexpr auto &os = cout;   // replace by cerr in interactive.
template<class C> static auto dud(C *x)->decltype(os << *x, 0);
template<class C> static char dud(...);
template<class C> typename enable_if<sizeof dud<C>(0)!=1, Dbg&>::type operator<<(const C &x) { os << x; return *this; }
template<class C> Dbg &dump(C b, C e) {
    *this << "\n[";
    int cur = 0;
    for (C i = b; i!=e and cur<26; i++, cur++) *this << ", "+2*(i==b) << *i;
    return *this << ']';
}
template<class C> typename enable_if<sizeof dud<C>(0)==1, Dbg&>::type operator<<(const C &x) {
    return dump(begin(x), end(x));
}
template<class C, size_t X> typename enable_if<!is_same<C, const char>::value, Dbg&>::type operator <<(C (&x)[X]) {
    return dump(begin(x), end(x));
}
template<class B, class C> Dbg &operator <<(const pair<B, C> &x) {
    return *this << '{' << x.first << ", " << x.second << '}';
}
template<class C, size_t Y> struct TP {
    void operator()(Dbg& os, const C &t) { TP<C, Y-1>()(os, t); os << ", " << get<Y-1>(t); }
};
template<class C> struct TP<C, 1> { void operator()(Dbg& os, const C &t) { os << get<0>(t); } };
template<class... C> Dbg& operator<<(const tuple<C...> &t) {
    os << '{', TP<decltype(t), sizeof...(C)>()(*this, t); return *this << '}';
}
Dbg &operator<<(ostream&(*x)(std::ostream&)) { os << x; return *this; }
} dbg;
void err(istringstream *iss) { delete iss; }
template<class C, class... Args> void err(istringstream *iss, const C &val, const Args &... args) {
    string name; *iss >> name; if (name.back()==',') name.pop_back();
    dbg << name << " = " << val << "; ", err(iss, args ...);
}
#define bug(args...) dbg << __LINE__ << ": ", err(new istringstream(string(#args)), args), dbg << endl
#define ASSERT(a, o, b) { if (!((a) o (b))) bug(a, b), assert((a) o (b)); }
#define sl(a) int(strlen(a))
#define sz(a) int(a.size())
int T, Q, cn;//}
const int inf = 1000000007, mxn = 100005;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<class key, class cmp = less<key>>
using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int n, a[mxn];

template<class C> C compress(vector<C> &v) {//{//prefer using unique+function with lower_bound when compressing combined vectors
    int sz = sz(v);
    vector<pair<C, int> > tmp(sz);
    for (int i = 0; i < sz; i++) {
        tmp[i] = {v[i], i};
    }
    sort(begin(tmp), end(tmp));
    int cur = 1;
    for (int i = 0; i < sz; i++) {
        cur += i and tmp[i]!=tmp[i-1];
        v[tmp[i].second] = cur;
    }
    return cur;
}//}

ll countRangesWithMeanGreater(int K, vector<int> &v) {

// For GreaterEqual change -inf to inf in order_of_key(): https://atcoder.jp/contests/arc075/tasks/arc075_c
/*
Traverse from left to right: when at 1, we need to check if cs[1]-cs[0]>K, when at 2, check if cs[2]-cs[1]>K and if
cs[2]-cs[0]>2*K. ==> going one element right, we need to increase all previous elements' checking by K, we can adjust
the new inserted element to that, i.e. we keep a ordered_multiset and query of how many elements < cs[i]-x, we increase
x by K every time we move to right, x = K at 1, when going from 1 to 2, x becomes 2K and we insert cs[1]-K, as:
cs[1]-K < cs[2]-2K is equivalent to cs[1] < cs[2]-K which is exactly what we need.
*/
    int sz = sz(v);
    vector<ll> cs(sz);
    partial_sum(begin(v), end(v), begin(cs));
    ll x = 0, ans = 0;
    ordered_set<pair<ll, int> > ost;
    ost.insert({0, -1});
    for (int i = 0; i < sz; i++) {
        x += K;
        ans += ost.order_of_key({cs[i]-x, -inf});
        ost.insert({cs[i]-x, i});
    }
    return ans;
}

ll countRangesWithMedianLessEqual(int x, vector<int> &v) {

// Definition of median is n/2+1 here.
/*
If we assign 1 to all elements <= x, number of ranges with median <=x is then ranges with mean > 1/2.
==> We can assign 2 instead, then mean > 1.
*/
    int sz = sz(v);
    vector<int> tmp(sz);
    for (int i = 0; i < sz; i++) {
        tmp[i] = v[i]<=x ? 2 : 0;
    }
    return countRangesWithMeanGreater(1, tmp);
}

signed main() { ios::sync_with_stdio(0); cin.tie(NULL); cout.precision(11);

// Definition of median is n/2+1 here.

/*We can convert the given sequence to a permutation of size n using sorted position of {a[i],i}, in order to differentiate
between equal elements. Median of median is definitely binary searchable, we need to check how many ranges have median<=x.*/

    cin >> n;
    vector<int> v(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i], v[i-1] = a[i];
    }
    compress(v);
    ll tot = n*ll(n+1)/2, medianPos = tot/2+1;
    int lo = 1, hi = n, ans = -1;
    while (lo<=hi) {
        auto mid = (lo+hi)>>1;
        if (countRangesWithMedianLessEqual(mid, v)>=medianPos) hi = mid-1, ans = mid;
        else lo = mid+1;
    }
    for (int i = 0; i < n; i++) {
        if (v[i]==ans) return cout << a[i+1] << '\n', 0;
    }
}

Measured memory_bytes: 8528