#include<bits/stdc++.h>
#define int long long
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    return f*x;
}
int a[100001],b[100001],n,ans,c[1000001],sum[100001];
int lowbit(int x){
	return x&(-x);
}
void Add(int x,int v){
	while(x<=n+200000)
		c[x]+=v,x+=lowbit(x);
}
int Sum(int x){
	int ans=0;
	while(x)
		ans+=c[x],x-=lowbit(x);
	return ans;
}
bool check(int x){
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1];
		if(a[i]<x)
			sum[i]++;
		else if(a[i]>x) sum[i]--;
	}
	int tot=0;
	for(int i=1;i<=n;i++)
		Add(sum[i]+200000,1),tot+=Sum(sum[i]+200000-1);
	for(int i=1;i<=n;i++)
		Add(sum[i]+200000,-1);
	return tot<(n*(n-1)/2+n)/2;
}
main(){
    //file("");
	n=read();
	for(int i=1;i<=n;i++)
		b[i]=a[i]=read();
	sort(b+1,b+1+n);
	int l=1,r=n;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(b[mid]))
			l=mid+1,ans=b[mid];
		else r=mid-1;
	}
	printf("%lld",ans);
    return 0;
}
