// Original C++ solution (slower):
#include<bits/stdc++.h>

//CLOCKS_PER_SEC

#define se second

#define fi first

#define ll long long

#define Pii pair<int,int>

#define Pli pair<ll,int>

#define ull unsigned long long

#define pb push_back

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const int N=1e5+10;

const int INF=0x3f3f3f3f;

const int mod=1e9+7;

using namespace std;

int n,val[N<<1];

int a[N],b[N];

int sum[N];

void add(int x){

	while(x<N*2){

		val[x]+=1;

		x+=x&-x;

	}

}

ll get(int x){

	ll ans=0;

	while(x>0){

		ans+=val[x];x-=x&-x;

	}

	return ans;

}

bool check(int x){

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

	ll tot=0;

	memset(val,0,sizeof(val));

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

		tot+=get(sum[i]+N);

		add(sum[i]+N);

	}

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

}

int main(){

	scanf("%d",&n);

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

		scanf("%d",&a[i]);b[i]=a[i];

	}

	sort(b+1,b+1+n);

	int l=1,r=n;

	int ans=1;

	while(l<=r){

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

		if(check(b[mid])){

			ans=mid;

			l=mid+1;

		}

		else r=mid-1;

	}

	cout<<b[ans]<<endl;

	return 0;

}  

// Optimized solution to the same problem (faster):
//Copyright(c)2018 Mstdream

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int N=200010;

int t[N],a[N],b[N],n;

void add(int x){

	for(;x<=2*n+1;x+=x&-x)t[x]++;

}

int qry(int x){

	int ret=0;

	for(;x;x-=x&-x)ret+=t[x];

	return ret;

}

bool check(int x){

	x++;

	LL ret=0;

	for(int i=1;i<=2*n;i++)t[i]=0;

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

		b[i]=(a[i]>=x?1:-1);

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

		add(b[i-1]+n+1);

		ret+=qry(b[i]+n+1);

	}

	ret=(LL)n*(n+1)/2-ret;

	return ret>=((LL)n*(n+1)/2+2)/2;

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

	int l=1,r=1e9+1;

	while(l!=r){

		int mid=l+r>>1;

		if(check(mid))r=mid;

		else l=mid+1;

	}

	cout<<l<<endl;

}


// 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;

}