#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAXN 100001
using namespace std;
int n,a[MAXN],s[MAXN],l,r,f[MAXN],b[MAXN];
struct data{int x,o;}c[MAXN];
bool cmp(const data &x,const data &y)
{
	return x.x<y.x;
}
void add(int x)
{
	while(x<=n) f[x]++,x+=x&-x;
	return ;
}
int query(int x)
{
	int tot=0;
	while(x>0) tot+=f[x],x-=x&-x;
	return tot;
}
bool check(int x)
{
	for(int i=1;i<=n;i++)
	{
		if(s[i]>=x) c[i].x=1;
		else c[i].x=0;
		c[i].x+=c[i-1].x;
		c[i].o=i;
	}
	sort(c+1,c+n+1,cmp);
	for(int i=1;i<=n;i++) b[c[i].o]=i;
	int ans=0;
	for(int i=1;i<=n;i++) add(b[i]),ans+=(i-query(b[i]));
	//for(int i=2;i<=n;i++) if
	ans=n*(n-1)/2-ans;
	return ans>n*(n-1)/4?true:false;
}
void slove()
{
	l=1,r=n;int mid;
	while(l<=r)
	{
		mid=l+r>>1;
		if(!check(s[mid])) r=mid-1;
		else l=mid+1;
	}
	cout<<s[mid];
	return;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],s[i]=a[i];
	sort(s+1,s+n+1);
	slove();
}