#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,a,b) for(int i = a;i <= b;i++)
using namespace std;
const int N = 1e5+100;
typedef long long ll;

int a[N];
int n;
int sum[N],xp[N];
ll tot,tmp;

void Merge(int l, int mid, int r)
{
	int i = 1, j = mid+1;
	rep(k,l,r)
		if(j > r || (i <= mid && sum[i] <= sum[j])) xp[k] = sum[i++];
		else xp[k] = sum[j++], tmp += mid-i+1;
//	printf("\n******\n");
	rep(k,l,r) sum[k] = xp[k]; // printf("%d ",sum[k]);
//	printf("\n******\n");
}

void Mergesort(int l,int r)
{
	if(l < r)
	{
		int mid = (l+r)>>1;
		Mergesort(l,mid);
		Mergesort(mid+1,r);
		Merge(l,mid,r);
	}
}

int check(int x)
{
	sum[0] = 0;
	tmp = 0;
	rep(i,1,n)
		if(a[i] <= x) sum[i] = 1;
		else sum[i] = -1;// tmp++;
	rep(i,1,n)
		sum[i] += sum[i-1];
	Mergesort(1,n);
//	printf("x:%d, tmp:%lld, tot:%lld\n",x,tmp,tot);
	if(tmp > (tot-tot/2-1)) return 0;
	else return 1;
}

int main()
{
	scanf("%d",&n);
	int l = 1e9, r = -1, ans;
	rep(i,1,n){
		scanf("%d",&a[i]);
		l = min(l,a[i]);
		r = max(r,a[i]);
	} 
	tot = n*(n+1)/2;
	while(l <= r)
	{
		int mid = (l+r)>>1;
		if(check(mid)){
		//	printf("Yes\n");
			ans = mid;
			r = mid-1;
		}
		else{
			l = mid+1;
		}
	}
	printf("%d\n",ans);
	return 0;
}