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

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

#define inl inline

#define re register

#define LL long long

#define MAXN 10100

using namespace std;

struct con

{

	int p;LL sum;

}hh[100100];

LL read()

{

    LL f=1,p=0;

    char c=getchar();

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

    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}

    return f*p;

}

void write(LL x)

{

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

    if(x/10)write(x/10);

    putchar(x%10+'0');

}

LL n,a[100100];

LL l=1000000000l,r,mid,ans,f[100100];

LL sum[100100];

inl LL lowbit(LL x){return x&(-x);}

inl bool cmp(const con&a,const con &b)

{

	if(a.sum==b.sum)return a.p<b.p;

	return a.sum<b.sum;

}

void add(int b){for(int i=b;i<=n;i+=lowbit(i))f[i]++;}

LL find(int a)

{

	LL u=0;

	for(int i=a;i>0;i-=lowbit(i))u+=f[i];

	return u;

}

bool check()

{

	ans=0;

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

	{

		if(a[i]<mid)hh[i].sum=-1;

		else hh[i].sum=1;

	}

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

		hh[i].sum+=hh[i-1].sum;

	for(int i=1;i<=n;i++)hh[i].p=i;

	sort(hh+1,hh+n+1,cmp);

	memset(f,0,sizeof(f));

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

	{

		add(hh[i].p);

		ans+=find(hh[i].p-1);

		if(hh[i].sum>=0)ans++; 

	}

	return 4*ans<n*(n+1);

}

int main()

{

	n=read();

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

	{

		a[i]=read();

		l=min(l,a[i]);

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

	}

	while(l<r)

	{

		mid=(l+r+1)/2;

		if(check()) r=mid-1;

		else l=mid;

	}

	write(l);

	return 0;

}

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

#include<algorithm>

#include<cmath>

using namespace std;

#define INF 1000000000;

int a[100005],sum[100005],save[100005];

typedef long long ll;

ll to,to1;

int n;int maxl,minl;

void sortl(int left,int right)

{

    if(left==right)

        return ;

    int mid=(right+left)/2;

    sortl(left,mid);

    sortl(mid+1,right);

    int l=left,l2=mid+1,r=left;

    while(l<=mid&&l2<=right)

    {

        if(sum[l]<sum[l2])

            save[r++]=sum[l++];

        else

        {

            to1+=l-left;

            save[r++]=sum[l2++];

        }

    }

    while(l<=mid)

        save[r++]=sum[l++];

    while(l2<=right)

    {

        to1+=l-left;

        save[r++]=sum[l2++];

    }

    for(int i=left;i<=right;i++)

        sum[i]=save[i];

}

bool ck(int x)

{

    to1=0;

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

        sum[i]=(a[i]<=x?1:-1);

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

        sum[i]+=sum[i-1];

    sortl(0,n);

    return to1>=to/2+1;

}

int main()

{

    maxl=-INF;minl=INF

    scanf("%d",&n);

    to=0;

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

    {

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

        minl=min(minl,a[i]);

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

        to+=i;

    }

    while(minl<maxl)

    {

        int mid=(minl+maxl)/2;

        if(ck(mid))

            maxl=mid;

        else

            minl=mid+1;

    }

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

}


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

}