#include<bits/stdc++.h>
using namespace std;
const int MAXN = 6e5+10;
typedef long long ll;
int lowbit(int i){return i&(-i);}
int n;
ll tree[MAXN];
void add(int i,ll v){
    for(;i<MAXN;i+=lowbit(i))tree[i]+=v;
}
ll query(int i){ll re=0;for(;i;i-=lowbit(i))re+=tree[i];return re;}
ll a[MAXN],pre[MAXN];
int b[MAXN];
int HF=MAXN/2;
bool solve(ll mid){
    ll re=0;memset(tree,0,sizeof(tree));
    for(int i=1;i<=n;++i){
        if(a[i]>=mid)b[i]=1;
        else b[i]=-1;
        pre[i]=pre[i-1]+b[i];
    }add(HF,1);
    for(int i=1;i<=n;++i){
        re+=query(pre[i]+HF);add(pre[i]+HF,1);
        
    }if(re*re>=(n*(n+1)/2+1))return true;
    return false;
}
ll x[MAXN];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]),x[i]=a[i];
    sort(x+1,x+1+n);int l=0,r=n,ans;
    while(l<=r){
        int mid=(l+r)>>1;
        if(solve(x[mid]))ans=x[mid],l=mid+1;
        else r=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}