    #include<bits/stdc++.h>
    using namespace std;
    const int N=300010;
    int n;
    int a[N],h[N],cnt,b[N];
    int s[N<<2];
    int lowbit(int k){return k&-k;}
    void add(int k)
    {
    	for(int i=k;i<=600010;i+=lowbit(i))
    		s[i]++;
    }
    int query(int k)
    {
    	int res=0;
    	for(int i=k;i;i-=lowbit(i))
    		res+=s[i];
    	return res;
    }
    bool check(int mid)
    {
    	long long res=0;
    	for(int i=1;i<=n;i++)
    		b[i]=(a[i]<=mid)?1:-1;
    	int sum=300010;
    	memset(s,0,sizeof(s));
    	add(300010);
    	for(int i=1;i<=n;i++)
    	{
    		sum+=b[i];
    		add(sum); res+=query(sum-1);
    	}
    	if(res<((1ll*n*(n-1)/2+n)/2+1))
    		return 0;
    	else
    		return 1;
    }
    int main()
    {
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)
    		scanf("%d",&a[i]),h[i]=a[i];
    	sort(h+1,h+n+1); cnt=unique(h+1,h+n+1)-h-1;
    	for(int i=1;i<=n;i++)
    		a[i]=lower_bound(h+1,h+cnt+1,a[i])-h;
    	int l=1,r=cnt;
    	while(l<r)
    	{
    		int mid=l+r>>1;
    		if(check(mid))r=mid;
    		else
    			l=mid+1;
    	}
    	printf("%d",h[l]);
    	return 0;
    }