// Problem: A. 中位数
// Contest: undefined - NOIP2024训练赛 05
// URL: http://119.28.3.174/contest/1157/problem/2380
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PII pair<int, int>

using namespace std;

const int N = 3e5 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m, q, ans, len;
int s[N], dp[N], cy[N], tr[(N << 1) + 1000];

inline int lowbit(int x) {return x & -x;}
inline void add(int x) {while(x <= 2 * n + 4) tr[x] ++, x += lowbit(x);}
inline int query(int x) {int res = 0; while(x) res += tr[x], x -= lowbit(x); return res;}

inline void init()
{
	sort(cy + 1, cy + n + 1);
	len = unique(cy + 1, cy + n + 1) - cy - 1;
	for(int i = 1; i <= n; i ++) s[i] = lower_bound(cy + 1, cy + len + 1, s[i]) - cy;
}

inline bool check(int x)
{
	// for(int i = 1; i <= 2 * n; i ++) tr[i] = 0; 
	memset(tr, 0, sizeof tr);
	int res = 0; add(dp[0]);
	for(int i = 1; i <= n; i ++) 
	{
		dp[i] = dp[i - 1] + (s[i] > x ? 1 : -1);
		res += query(dp[i]);
		add(dp[i]);
	}
	return res >= n * (n + 1) / 2 / 2;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i ++) {cin >> s[i]; cy[i] = s[i];}
	init();
	int l = 1, r = len, res = 0; dp[0] = len; 
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(check(mid)) l = mid + 1, res = mid;
		else r = mid - 1;
	}
	// cout << "res = " << res << '\n';
	cout << cy[res] << '\n';
	return 0;
}