#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define inl inline
#define re register
#define LL long long
#define MAXN 10100
using namespace std;
struct con
{
	int p;LL sum;
}hh[100100];
LL read()
{
    LL f=1,p=0;
    char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return f*p;
}
void write(LL x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)write(x/10);
    putchar(x%10+'0');
}
LL n,a[100100];
LL l=1000000000l,r,mid,ans,f[100100];
LL sum[100100];
inl LL lowbit(LL x){return x&(-x);}
inl bool cmp(const con&a,const con &b){return a.sum<b.sum;}
void add(int a,int b){for(int i=b;i<=n;i+=lowbit(i))f[i]++;}
LL find(int a)
{
	LL u=0;
	for(int i=a;i>0;i-=lowbit(i))u+=f[i];
	return u;
}
bool check()
{
	ans=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]<mid)hh[i].sum=-1;
		else hh[i].sum=1;
	}
	for(int i=1;i<=n;i++)
		hh[i].sum+=hh[i-1].sum;
	for(int i=1;i<=n;i++)hh[i].p=i;
	sort(hh+1,hh+n+1,cmp);
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		add(hh[i].sum,hh[i].p);
		ans+=find(hh[i].p-1);
	}
	return 4*ans<n*(n+1)+4;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		l=min(l,a[i]);
		r=max(r,a[i]);
	}
	while(l<r)
	{
		mid=(l+r+1)/2;
		if(check()) l=mid+1;
		else r=mid;
	}
	write(l);
	return 0;
}