// Original C++ solution (slower):
/*

  mail: mleautomaton@foxmail.com

  author: MLEAutoMaton

  This Code is made by MLEAutoMaton

*/

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<iostream>

using namespace std;

#define ll long long

#define re register

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

inline int gi(){

	int f=1,sum=0;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

const int N=100010;

int a[N],b[N],n,tot,p[N],c[N<<2],Mx;

ll cnt;

int lowbit(int x){return x&(-x);}

void Add(int x,int d){while(x<=Mx){c[x]+=d;x+=lowbit(x);}}

int sum(int x){int ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret;}

bool check(int mid){

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

		if(p[i]<mid)a[i]=-1;

		else a[i]=1;

	ll ans=0;

	for(int i=1;i<=n;i++){a[i]+=a[i-1];if(a[i]>=0)ans++;}

	memset(c,0,sizeof(c));Mx=0;

	for(int i=1;i<=n;i++){a[i]+=n+1;Mx=max(Mx,a[i]);}

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

		ans+=sum(a[i]);

		Add(a[i],1);

	}

	return cnt-ans<cnt/2+1;

}

int q[100010];

int main(){

	n=gi();

	for(int i=1;i<=n;i++)p[i]=q[i]=gi();

	sort(q+1,q+n+1);int tot=unique(q+1,q+n+1)-q-1;

	for(int i=1;i<=n;i++)p[i]=lower_bound(q+1,q+tot+1,p[i])-q;

	int l=1,r=tot,ans=0;cnt=1ll*n*(n-1)/2ll+n;

	while(l<=r){

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

		if(check(mid)){ans=mid;l=mid+1;}

		else r=mid-1;

	}

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

	return 0;

}


// Optimized solution to the same problem (faster):
// ===================================

//   author: M_sea

//   website: http://m-sea-blog.com/

// ===================================

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define re register

using namespace std;

typedef long long ll;



inline int read() {

    int X=0,w=1; char c=getchar();

    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }

    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

    return X*w;

}



const int N=100000+10;



int n,mx;

int a[N],s[N],S[N];



int c[N<<1];

inline int lowbit(int x) { return x&-x; }

inline void add(int x,int y) {

    for (;x<=mx;x+=lowbit(x)) c[x]+=y;

}

inline int query(int x) {

    int res=0;

    for (;x;x-=lowbit(x)) res+=c[x];

    return res;

}



inline int check(int mid) {

    memset(c,0,sizeof(c)),mx=0;

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

        if (a[i]<mid) s[i]=-1;

        else s[i]=1;

    }

    ll res=0;

    for (re int i=1;i<=n;++i) s[i]+=s[i-1],res+=(s[i]>=0);

    for (re int i=1;i<=n;++i) s[i]+=n+1,mx=max(mx,s[i]);

    for (re int i=1;i<=n;++i) res+=query(s[i]),add(s[i],1);

    ll cnt=1ll*n*(n-1)/2+n;

    return cnt-res<cnt/2+1;

}



int main() {

    n=read();

    for (re int i=1;i<=n;++i) S[i]=a[i]=read();

    sort(S+1,S+n+1); int m=unique(S+1,S+n+1)-S-1;

    for (re int i=1;i<=n;++i) a[i]=lower_bound(S+1,S+m+1,a[i])-S;

    int L=1,R=m,ans=0;

    while (L<R) {

        int mid=(L+R+1)>>1;

        if (check(mid)) L=mid;

        else R=mid-1;

    }

    printf("%d\n",S[L]);

    return 0;

}


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

}