#include <bits/stdc++.h>
#include<chrono>
#define ll long long
using namespace std;
vector<ll>bit;
ll MOD = 1e9 + 7;
ll A, B, H, N, M, L, K, W, X, Y, Z;
ll ans = 0;
void add(ll a, ll w) {
	for (int x = a; x < 2*N; x += x & -x) {
		bit[x] += w;
	}
}
int sum(ll a) {
	int res = 0;
	for (int x = a; x > 0; x -= x & -x)res += bit[x];
	return res;
}

int main() {
	cin >> N;
	vector<ll>a(N+1),b(N+1),csum(N+2),copy(3*N,0);
	ll r = 0;
	ll l = 0;
	for (int i = 1; i < N+1; i++) {
		cin >> a[i];
		r = max(r, a[i]);
	}
	while (l<=r) {
		bit = copy;
		ll mid = (r + l) / 2;
		csum[1] = 0;
		for (int i = 1; i < N + 1; i++) {
			if (a[i] >= mid)b[i] = 1;
			else b[i] = -1;
			csum[i + 1] = csum[i] + b[i];
		}
		ll invN = 0;
		for (int i = 1; i < N + 2; i++) {
			invN += sum(csum[i]+N);
			add(csum[i]+N, 1);
		}
		if (invN >= N*(N+1)/4)l = mid+1;
		else r = mid - 1;;
	}
	cout << r << endl;
}
