#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
int ps[300005];
int a[300005],tree[700010],tong[600006];
int b[300005];
int n;
void upd(int pos,int add){
	for(int i = pos;i<2*n+5;i+=lowbit(i))tree[i]+=add;
}int query(int pos){int res =0 ;
	for(int i = pos;i>0;i-=lowbit(i))res+=tree[i];return res;
}bool check(int x){
	long long tot = 0,s =0,l = ((long long)n*(n+1)/2+1)/2;
	for(int i =0;i<2*n+5;i++)tree[i] = tong[i] = 0;
	int pos = 0;
	for(int i = 1;i<=n;i++){
		if(a[i] == x)b[i] = 0,pos= i;
		if(a[i]<x)b[i] = -1;
		if(a[i]>x)b[i] = 1;
	}int xx = n+1;
	for(int i = 1;i<=n;i++){
		upd(s+xx,1);s+=b[i];
		tot=tot+query(xx+s-1);
	//	cout << s << " " << tot << endl;
	}s = 0;
	for(int i = 1;i<=pos;i++)s+=b[i];tong[s+x]++;
	for(int i = pos+1;i<=n;i++)s+=b[i],tong[s+x]++;s=0;
	for(int i =0;i<pos;i++){
		s+=b[i];tot+=tong[x+s];
	}//cout << x << " " << tot << " " << l << endl;
	return (tot>=l);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i<=n;i++)cin >>a[i];
	vector<pair<int,int> >p;
	for(int i =1;i<=n;i++)p.push_back({a[i],i});
	sort(p.begin(),p.end());
	for(int i =0;i<p.size();i++)a[p[i].second] = i+1,ps[i+1] = p[i].first;
	int l = 1,r = n;
	while(l<r){
		int mid = l+r+1>>1;
		if(check(mid))l = mid;
		else r = mid-1;
	}cout << ps[l] << endl;
}/*
20
9 14 19 20 2 2 9 13 10 15 20 3 16 7 9 19 1 2 14 1 
*/