#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define ppll pair<ll,pll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
// #define ll int
using namespace std;
const ll INF = 1 << 29;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const int MAX_V = 500;
const ll mod = 998244353;
const ll MAX = 2100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[8] ={1,0,-1,0,1,-1,1,-1};
ll dy[8] ={0,1,0,-1,1,-1,-1,1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T, class S> ostream &operator<<(ostream &os, const pair<T, S> &p)
{ cout << "(" << p.first << ", " << p.second << ")"; return os; }
template <class T, class S> istream& operator>>(istream& os,  pair<T, S>& p)
{ os >> p.first >> p.second; return os; }
template <class T> ostream &operator<<(ostream &os, const vector<T> &v)
{ for (auto &e : v){cout << e << " ";}cout << endl;return os; }




template<class T>
struct BIT {
    ll n;
    vector<T> bit;

    // bit_i is 1-indexed
    // 各要素の初期値は 0
    BIT(ll num) : bit(num+1, 0) { n = num; }

    // a_i += w
    void add(ll i, T w) {
        for (ll x = i; x <= n; x += x & -x) {
            bit[x] += w;
        }
    }
    // [1, i] の和を計算.
    T sum(ll i) {
        T ret = 0;
        for (ll x = i; x > 0; x -= x & -x) {
            ret += bit[x];
        }
        return ret;
    }

    // [a,b)の和を計算
    T sum(ll a, ll b) {
        return sum(b-1) - sum(a-1);

    }

    // bit[i] の最大値を w に更新
    void add_max(ll i,T w) {
        for (ll x = i; x <= n; x += x & -x) {
            chmax(bit[x],w);
        }
    }

    // [1,i]の最大値を計算.
    T max(ll i) {
        T ret=0;
        for (ll x = i; x > 0; x -= x & -x) {
            chmax(ret,bit[x]);
        }
        return ret;
    }

    
    // v1 + v2 + ⋯ + vx >= w となる最小の x を求める
    // w 番目に小さい要素を見つけるset
    ll lowerBound(ll w) {
        if(w <= 0) return 0;
        ll x = 0;
        ll k = 1;
        while(k * 2 <= n) k*=2;
        for(; k > 0; k /= 2){
            if(x + k <= n && bit[x + k] < w){
                w -= bit[x + k];
                x += k;
            }
        }
        return x + 1;
    }

    // debug 
    void print() {
        for (ll i = 1; i < n+1 ; i++) {
            cout<<sum(i,i+1)<<", ";
        }
        cout<<endl;
    }
    
};






void solve() {
    ll n;
    ll a[100010];
    cin>>n;
    rep(i,n){
        cin>>a[i];
    }
    if(n==1){
        cout<<a[0]<<endl;
        return;
    }

    ll left = 0, right = LLINF;

    while(right - left > 1) {
        ll mid = (left + right) / 2;
        ll b[100010];
        rep(i,n){
            if(a[i] < mid) b[i] = -1;
            else b[i] = 1;
        }
        ll sum[100010]={};
        rep(i,n){
            sum[i+1] = sum[i] + b[i];
        }
        rep(i,n+1) sum[i] += n + 1;
        BIT<ll> bit(2*(n+1));
        ll ans = 0;
        rep(i,n+1){
            ans += bit.sum(sum[i]);
            bit.add(sum[i], 1);
        }
        if(ans < n*(n+1)/2/2){
            right = mid;
        }
        else left = mid;
    }
    cout<<left<<endl;



}






signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);


    ll t=1;
    
    // cin>>t;

    rep(i,t){
        solve(); 
    }

    return 0;
}


Measured memory_bytes: 7520