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

#include<cstdio>

#include<map>

#include<algorithm>

using namespace std;

const int MAXN = 100010;

long long sum[MAXN];

int a[MAXN],aa[MAXN],b[MAXN],c[MAXN];

int n;

int lowbit(int x){return x&(-x);}

void update(int x,int n){

	for (int i=x;i<=n;i+=lowbit(i)) {

		sum[i]++;

	}

}

int getSum(int x) {

	int ans = 0;

	for (int i=x;i>0;i-=lowbit(i)) {

		ans += sum[i];

	}

	return ans;

}

long long check(int x) {

	b[0] = 0;c[0] = 0;

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

		if (a[i]<=x) b[i] = 1;

		else b[i] = -1;

	}

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

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

		c[i] = b[i];

	}

	sort(c,c+1+n);

	int cnt = 1;

	map<int,int> mp;

	mp[c[0]] = 1;

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

		if (c[i]!=c[i-1]) {

			cnt++;

			mp[c[i]] = cnt;

		}

	}

	for (int i=0;i<=cnt;i++) sum[i]=0;

	long long res = 0;

	update(mp[0],cnt);

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

		res += getSum(mp[b[i]]-1);

		update(mp[b[i]],cnt);

	}

	return res;

}

int main()

{

	scanf("%d",&n);

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

	for (int i=1;i<=n;i++) aa[i] = a[i];

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

	long long k = 1LL * n*(n+1)/2/2+1;

	int l = 1,r = n,mid,ans;

	while(l<=r) {

		mid = (l+r) / 2;

		if (check(aa[mid])>=k) {

			ans = aa[mid];

			r = mid - 1;

		}

		else l = mid + 1;

	}

	printf("%d\n",ans);

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

using namespace std;

#define fo(i,a,b) for(int i=a;i<=b;i++)

#define fd(i,a,b) for(int i=a;i>=b;i--)

int n,a[110000],l,r,mi,f[220000];

long long m;

inline void add(int x){

	while (x<=n+n){

		f[x]++;

		x+=x&(-x);

	}

}

inline long long ask(int x){

	long long ans=0;

	while (x){

		ans+=f[x];

		x-=x&(-x);

	}

	return ans;

}

inline bool che(int x){

	int s=n+1;long long ans=0;//s=n TLE

	fo(i,0,n+n) f[i]=0;

	add(s);

	fo(i,1,n){

		if (a[i]>=x) s++;else s--;

		ans+=ask(s);

		add(s);

	}

	return ans>=m;

}

int main(){

	scanf("%d",&n);

	fo(i,1,n) scanf("%d",&a[i]);

	m=n*1ll*(n+1)/2;

	m=(m+1)/2;

	l=0x7fffffff;r=0;

	fo(i,1,n){

		if (a[i]<l) l=a[i];

		if (a[i]>r) r=a[i];

	}

	l--;r++;

	while (l+3<r){

		mi=(l+r)>>1;

		if (che(mi)) l=mi+1;else r=mi-1;

	}

	fd(i,r+1,l-1) if (che(i)){//che(mi)!!!

		printf("%d\n",i);

		return 0;

	}

	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;

}