#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,s[100500];
ll solve(ll p) {
    vector<ll> k(2*n+1);
    ll sum=n;
    k[sum]=1;
    ll add=1;
    ll res=0;
    for(int i=1;i<=n;i++) {
        if(s[i]<p) {
            add-=k[sum];
            sum--;
        }
        else {
            
            sum++;
            add+=k[sum];

        }
        res+=add;
        k[sum]++;
        add++;    
    }
    return res;
}


int main() {
     ll l=INT_MAX,r=INT_MIN,res=INT_MIN;
     cin>>n;
     for(int i=1;i<=n;i++) {
         cin>>s[i];
         l=min(l,s[i]);
         r=max(r,s[i]);
     }
     if(l==r)
     {
        cout<<l<<endl;
        return 0;
     }
    ll tot=n*(n+1)/2-(n*(n+1)/4+1);
     while(l<=r) {
        ll mid=(l+r)>>1;
        ll ans=solve(mid);
        if(ans<tot) {
            r=mid-1;

        }
        else {
            res=max(mid,res);
            l=mid+1;

        }
     } 
     cout<<res<<endl;  
}