#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template< typename T >
struct BinaryIndexedTree {
	vector< T > data;

	BinaryIndexedTree(int sz) {
		data.assign(++sz, 0);
	}

	T sum(int k) {
		T ret = 0;
		for(++k; k > 0; k -= k & -k) ret += data[k];
		return (ret);
	}

	void add(int k, T x) {
		for(++k; k < data.size(); k += k & -k) data[k] += x;
	}
};

signed main() {
	ll N;
	scanf("%lld", &N);
	vector<ll> a(N, 0);
	for(ll i=0; i<N; i++) scanf("%lld", &a[i]);
	if(N==1){
		printf("%lld\n", a[0]);
		return 0;
	}

	ll left = 0;
	ll right = 1e9+1;
	auto isOK = [&](ll val) -> bool {
		vector<ll> b(N,0);
		for(ll i=0; i<N; i++) b[i] = (a[i]<val ? -1 : 1);
		vector<ll> rui(N+1, 0);
		for(ll i=0; i<N; i++) rui[i+1] = rui[i] + b[i];
		for(ll i=0; i<N+1; i++) rui[i] += N;

		BinaryIndexedTree<ll> bit(2*N);
		ll tentosu=0;
		for(ll i=0; i<N+1; i++) {
			tentosu += i - bit.sum(rui[i]);
			bit.add(rui[i], 1);
		}
		ll t = N*(N+1)/2 - tentosu;
		return t >= N*(N+1)/2/2;
	};

	while(right - left > 1) {
		ll mid = left + (right - left) / 2;
		if(isOK(mid)) left = mid;
		else right = mid;
	}

	printf("%lld\n", left);
	return 0;
}
