#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN] , binary[MAXN];
int n;
int s[MAXN] , pre[MAXN];
int c[MAXN * 2];
#define lowbit(i) i&-i
#define mid ((l+r)>>1)
inline void add(int x)
{
	for(int i = x ; i <= n*2+1 ; i+=lowbit(i))
		c[i] += 1;
}
inline int getsum(int x)
{
	int res = 0;
	for(int i = x ; i >= 1 ; i-=lowbit(i))
		res += c[i];
	return res;
}
inline int query(int x)
{
	return getsum(n*2 + 1) - getsum(x);
}
inline int nxd()
{
	memset(c,0,sizeof(c));
	int ans = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		add(pre[i] + n + 1);
		ans += query(pre[i] + n + 1);
		//前面有多少个比pre[i]大 
	}
	return ans;
}
inline int cnt(int x)//求新数列里有多少个数比x小 
{
	//a[i]小于等于x,s[i]就为-1 ,否则为1 
	for(int i = 1 ; i <= n ; i++)
		s[i] = (a[i] <= x) ? -1 : 1;
	//接下来求s数组有多少个子区间和小于0,若小于0,则代表比x小的数比比x大的数多，所以x>该区间中位数 
	pre[0] = 0;
	for(int i = 1 ; i <= n ; i++)
		pre[i] = pre[i-1] + s[i];
	//sum(s[l]~s[r]) = pre[r] - pre[l-1] < 0 
	//所以转为求pre数组逆序对
	return nxd(); 
}
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; i++)
		scanf("%d",a+i) , binary[i] = a[i];
	sort(binary+1,binary+n+1);
	int l = 1 , r = n;
	int m = (n + 1) * n / 2;
	while(l < r)
	{
		int x = cnt(binary[mid]);
		if(x > m / 2 + 1)//猜的数大于等于中位数，尽量小 
			r = mid;
		else
			l = mid + 1;
	}
	printf("%d\n",binary[l]);
}