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

#include<cstdlib>

#include<iostream>

#include<cstring> 

#include<algorithm>

using namespace std;

typedef long long ll;

int tree[300000+10];

int a[100000+10];

int c[100000+10];

int n;

int lowbit(int x){

	return x&-x;

}

void update(int x){

	while(x<=200020){

		tree[x]++;

		x+=lowbit(x);

	}

}

ll query(int x){

	ll res=0;

	while(x>0){

		res+=tree[x];

		x-=lowbit(x);

	}

	return res;

}

bool check(int x){

	c[0]=0;

	for(int i=1;i<=n;i++) c[i]=c[i-1]+(a[i]>=x ? 1:-1);

	memset(tree,0,sizeof(tree));

	ll sum=0;

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

		sum+=query(c[i]+100010);

		update(c[i]+100010);

	}

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

}

int main(){

	while(~scanf("%d",&n)){

		int l=0,r=-1000000000;

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

			scanf("%d",&a[i]);

			r=max(a[i],r);

		}

//		printf("%d %d\n",l,r);

		while(l<=r){

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

			if(check(mid)) l=mid+1; else r=mid-1;

		}

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

	}

	return 0;

} 

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h> //Ithea Myse Valgulious

namespace chtholly{

typedef long long ll;

#define re0 register int

#define rel register ll

#define rec register char

#define gc getchar

#define pc putchar

#define p32 pc(' ')

#define pl puts("")

/*By Citrus*/

inline int read(){

  int x=0,f=1;char c=gc();

  for (;!isdigit(c);c=gc()) f^=c=='-';

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return f?x:-x;

  }

template <typename mitsuha>

inline bool read(mitsuha &x){

  x=0;int f=1;char c=gc();

  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';

  if (!~c) return 0;

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return x=f?x:-x,1;

  }

template <typename mitsuha>

inline int write(mitsuha x){

  if (!x) return 0&pc(48);

  if (x<0) pc('-'),x=-x;

  int bit[20],i,p=0;

  for (;x;x/=10) bit[++p]=x%10;

  for (i=p;i;--i) pc(bit[i]+48);

  return 0;

  }

inline char fuhao(){

  char c=gc();

  for (;isspace(c);c=gc());

  return c;

  }

}using namespace chtholly;

using namespace std;

const int yuzu=1e5;

typedef int fuko[yuzu<<1|10];

struct _bit{

fuko c;

void init(){memset(c,0,sizeof c);}

void add(int x){for (;x<=yuzu<<1;x+=x&-x) c[x]++;}

int query(int x){

  int llx=0;

  for (;x;x&=x-1) llx+=c[x]; 

  return llx;

  }

}my_;

fuko b,a;

bool judge(int x,int n,int i=1){

my_.init();

for (;i<=n;++i) b[i]=b[i-1]+(a[i]>=x?1:-1);

ll llx=0;

for (i=0;i<=n;++i) llx+=my_.query(b[i]+yuzu),my_.add(b[i]+yuzu);

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

}

int main(){

int i,n=read(),l=0,r=0;

for (i=1;i<=n;++i) r=max(a[i]=read(),r);

for (;l<=r;){

  int mid=l+r>>1;

  judge(mid,n)?l=mid+1:r=mid-1;

  }

write(l-1);

}

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

}