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

#include <cstring>

#include <cstdlib>

#include <cctype>

#include <iostream>

#include <algorithm>

#include <ext/pb_ds/hash_policy.hpp>

#include <ext/pb_ds/assoc_container.hpp>

#include <queue>

#define ri register int 

#define ll long long 

#define ull unsigned long long 

using std::min;

using std::max;

using std::lower_bound;

using namespace __gnu_pbds;

template <class T>inline void read(T &x){

    x=0;int ne=0;char c;

    while(!isdigit(c=getchar()))ne=c=='-';

    x=c-48;

    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;

    x=ne?-x:x;return ;

}

const int maxn=200005;

const int inf=0x7fffffff;

int n,nn,a[maxn],b[maxn],c[maxn],mx=-inf,mi=inf;

ll sum[maxn<<2];

inline void update(int x,int d){for(;x<=nn;x+=x&(-x))sum[x]+=d;}

inline ll query(int x){ll ans=0;for(;x;x-=x&(-x))ans+=sum[x];return ans;}

inline ll chk(int k){

    ll ans=0;

    b[0]=0;

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

        b[i]=b[i-1]+((a[i]<=k)?1:-1);

        c[i]=b[i];

        ans+=(b[i]>0);

    }

    std::sort(c+1,c+1+n);

    nn=std::unique(c+1,c+1+n)-(c+1);

    memset(sum,0,sizeof(sum));

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

    	b[i]=lower_bound(c+1,c+1+nn,b[i])-c;

        ans+=query(b[i]-1);

        update(b[i],1);

    }

    return ans;

}

int main(){

    read(n);

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

        read(a[i]);

        mi=min(mi,a[i]),mx=max(mx,a[i]);

    }

    int L=mi,R=mx,mid,ans;

	ll lim=1ll*n*(n+1)/4+1;

    while(L<=R){

        mid=(L+R)>>1;

        if(chk(mid)>=lim)ans=mid,R=mid-1;

        else L=mid+1;

    }

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

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<set>

#define MN 100005

using namespace std;

int n,tt,a[MN],num[MN],tmp[MN],tmpx[MN];

long long tx;

void mergesort(int ll,int rr){

	if(ll==rr)return;

	int mid=(ll+rr)>>1;

	mergesort(ll,mid),mergesort(mid+1,rr);

	int tl=ll,tr=mid+1,now=0;

	while(tl<=mid&&tr<=rr){

		if(tmp[tl]<tmp[tr])tmpx[++now]=tmp[tl++];

		else {

			tx+=tl-ll;

			tmpx[++now]=tmp[tr++];

		}

	}

	while(tl<=mid)tmpx[++now]=tmp[tl++];

	while(tr<=rr)tx+=tl-ll,tmpx[++now]=tmp[tr++];

	for(int i=ll,j=1;i<=rr;i++,j++)tmp[i]=tmpx[j];

}

bool check(int mid){

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

		tmp[i]=tmp[i-1]+(a[i]<=mid?1:-1);

	tx=0;mergesort(0,n);

	return tx>=(1ll*n*(n+1)/4+1);

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]),num[++tt]=a[i];sort(num+1,num+tt+1);tt=unique(num+1,num+n+1)-num;

	int l=1,r=tt-1,ans=tt-1;

	while(l<=r){

		int mid=(l+r)>>1;

		if(check(num[mid]))ans=mid,r=mid-1;

		else l=mid+1;

	}printf("%d\n",num[ans]);

}

// 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;

}