// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define ll long long

#define lowbit(a) a&(-a)

#define INF 0x3f3f3f3f

using namespace std;



inline int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return f*sum;

}



const int N=100001;

ll n,a[N];ll s[N];

ll c[N],tot;ll t[(N<<1)+5];



inline ll ask(int x){

	ll ret=0;

	for(int i=x;i;i-=lowbit(i)) ret+=t[i];

	return ret;

}



inline void add(int x,int k){

	for(int i=x;i<=(N<<1);i+=lowbit(i)) t[i]+=k;

}



inline bool check(int mid){

	memset(t,0,sizeof(t));s[0]=0;ll sum=0;

	for(int i=1;i<=n;i++) s[i]=s[i-1]+(a[i]>=mid? 1:-1);

	for(int i=0;i<=n;i++){

		sum+=ask(s[i]+N);add(s[i]+N,1);

	}

	return sum>=n*(n+1)/4;

}



int main(){

	n=read();

	for(int i=1;i<=n;i++) a[i]=read(),c[i]=a[i];

	sort(c+1,c+n+1);int m=unique(c+1,c+n+1)-c-1;

	for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+m+1,a[i])-c;

	int l=1,r=n;

	while(l<=r){

		int mid=(l+r)>>1;

		if(check(mid)) l=mid+1;

		else r=mid-1;

	}

	printf("%lld\n",c[r]);

	return 0;

}


// Optimized solution to the same problem (faster):
#include<iostream>

#define int long long

using namespace std;

int a[1000001],n,ans;

int s[1000001],c[5000001];

int lowbit(int x)

{

	return x&(-x);

}

void add(int x,int d)

{

	for (;x<=n*4;x+=lowbit(x))

		c[x]+=d;

	return;

}

int sum(int x)

{

	ans=0;

	for (;x>=1;x-=lowbit(x))

		ans+=c[x];

	return ans;

}

bool check(int x)

{

	for (int i=1;i<=n*4;++i)

		c[i]=0;

	s[0]=0;

	int res=0;

	for (int i=1;i<=n;++i)

	{

		if (a[i]>=x)

			s[i]=s[i-1]+1;

		else

			s[i]=s[i-1]-1;

	}

	for (int i=0;i<=n;++i)

	{

		res+=sum(s[i]+n+1);

		add(s[i]+n+1,1);

	}

	return res>=(n+1)*n/4;

}

signed main()

{

	int first,last,mid,ans=-(1e+9),minn=1e+9,maxn=-(1e+9);

	cin>>n;

	for (int i=1;i<=n;++i)

	{

		cin>>a[i];

		maxn=max(maxn,a[i]);

		minn=min(minn,a[i]);

	}

	first=minn;

	last=maxn;

	ans=minn;

	while (first<=last)

	{

		mid=(first+last)/2;

		if (check(mid))

		{

			ans=max(ans,mid);

			first=mid+1;

		}

		else

			last=mid-1;

	}

	cout<<ans<<endl;

	return 0;

}

// Fastest known solution for this problem:
#define _USE_MATH_DEFINES



#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

#include <list>

#include <stack>



using namespace std;



typedef pair<long long int, long long int> P;



long long int INF = 1e18;

long long int MOD = 1e9 + 7;



long long int N, sz = 150000;

long long int A[110000];

bool flag[110000];

long long int BIT[210000];



void add(int a, long long int w){

	

	// a番目の要素にwを足す O(log N)

	

	for(int x = a; x <= sz; x += x & -x){

		BIT[x] += w;

	}

}



long long int sum(int a){

	

	// 1からaまでの要素の合計を返す O(log N)

	

	long long int ret = 0;

	for(int x = a; x > 0; x -= x & -x){

		ret += BIT[x];

	}

	return ret;

}



void init(){

	for(int i = 0; i < sz; i++){

		BIT[i] = 0;

	}

}



bool check(long long int min_A){

	for(int i = 0; i < N; i++){

		flag[i] = (A[i] >= min_A);

	}

	vector<P> v;

	long long int cnt = 0, S = 0;

	v.push_back(make_pair(0, 1));

	for(int i = 0; i < N; i++){

		if(flag[i]){

			S += 1;

		}else{

			S -= 1;

		}

		v.push_back(make_pair(S, i + 2));

	}

	sort(v.begin(), v.end());

	init();

	for(int i = 0; i < v.size(); i++){

		cnt += sum(v[i].second);

		add(v[i].second, 1);

	}

	//cout << min_A << " " << cnt << endl;

	return cnt >= (N * (N + 1) / 2 + 1) / 2;

}



long long int bin_search(long long int lef, long long int rig){

	long long int middle = (lef + rig) / 2;

	//cout << middle << " ";

	if(rig - lef <= 1){

		if(check(rig)){

			return rig;

		}else{

			return lef;

		}

	}

	if(check(middle)){

		lef = middle;

	}else{

		rig = middle;

	}

	return bin_search(lef, rig);

}



int main(){

	

	cin >> N;

	

	for(int i = 0; i < N; i++){

		cin >> A[i];

	}

	

	cout << bin_search(0, 1e10) << endl;

	

	return 0;

}