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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define in read()

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

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

#define xx 100001

#define ll long long

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	for(;!isalnum(ch);ch=getchar()) if(ch=='-') f=-1;

	for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';

	return x*f;

}

ll a[xx],cha[xx],ru[xx*2];

ll n;

inline void cot(ll k,ll x)

{

	while(k<xx*2)

	{

		ru[k]+=x;

		k+=(k&-k);

	}

}

inline ll get(ll k)

{

	ll ans=0;

	while(k>0)

	{

		ans+=ru[k];

		k-=(k&-k);

	}

	return ans;

}

inline bool check(ll k)

{

	memset(ru,0,sizeof(ru));

	cha[0]=0;

	fur(i,1,n) cha[i]=cha[i-1]+(a[i]>=k?1:-1);

	ll ans=0;

	fur(i,0,n)

	{

		ans+=get(cha[i]+xx);

		cot(cha[i]+xx,1ll);

	}

	return ans>=(n*(n+1)>>2);

}

int main()

{

	ll l=0,r=0;

	n=in;

	fur(i,1,n) a[i]=in,r=max(a[i],r);

	while(l<=r)

	{

		ll mid=l+r>>1;

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

		else r=mid-1;

	}

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

	return 0;

}

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

using namespace std;



const int N = 110000;



int a[N], sum[N];

int BIT[3 * N];



int main() {

	

	ios::sync_with_stdio(0);

	cin.tie(0), cout.tie(0);

	

	int n; cin >> n;

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

	

	int st = 0, en = 1e9, mid, ans = en;

	

	auto add = [&](int u, int v) {

		for (int i = u; i <= 3 * (n + 1); i += i & -i) BIT[i] += v;

	};

	

	auto get = [&](int u) {

		int ret = 0;

		for (int i = u; i > 0; i -= i & -i) ret += BIT[i];

		return ret;

	};

	

	auto can = [&](int mid) {

		sum[0] = 0;

		for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + 2 * (a[i] <= mid);

		for (int i = 0; i <= 3 * (n + 1); i++) BIT[i] = 0;

		long long cnt = 0;

		add(0 + n + 1, 1);

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

			cnt += get(sum[i] - i + n);

			add(sum[i] - i + n + 1, 1);

		}

		return cnt * 2 > (long long)n * (n + 1) / 2;

	};

	

	while (st <= en) {

		mid = st + en >> 1;

		if (can(mid)) ans = mid, en = mid - 1;

		else st = mid + 1;

	}

	cout << ans << "\n";

	

	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;

}