// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

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

long long m;

namespace BIT

{

	long long c[500005];

	inline long long lowbit(long long x) { return x & (~x + 1); }

	inline void add(long long x, long long val)

	{

		for (long long i = x; i < 4 * n; i += lowbit(i))	c[i] += val;

	}

	inline long long sum(long long x)

	{

		long long res = 0;

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

		return res;

	}

}

bool check(int x)

{

	long long cnt = 0;

	sum[0] = 0;

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

	{

		sum[i] = (a[i] >= x);

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

	}

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

	{

		sum[i] = (2 * sum[i] - i) + n + 1;

	}

	memset(BIT::c, 0, sizeof(BIT::c));

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

	{

		cnt += BIT::sum(sum[i]);

		BIT::add(sum[i], 1);

	}

	return cnt >= (m+1)/2;

}

int main()

{

	int l = 1000000005, r = 1, ans, mid;

	scanf("%d", &n);

	m = 1ll*n * (n + 1) / 2;

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

	{

		scanf("%d", a + i);

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

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

	}

	while (l <= r)

	{

		mid = (l + r) >> 1;

		if (check(mid))	l = mid + 1, ans = mid;

		else r = mid - 1;

	}

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

	return 0;

}


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

//#define IORD

#define eps 1e-8

#define inf 0x3f3f3f3f

//#define mod (1000000007)



using namespace std;

typedef long long LL;

typedef pair<int,int> pp;



const int N=1e5+10;

const int maxn=N*2+10;

int n,a[N],b[N],ais[N];

LL cnt=0;



int bit[maxn+1];

int lb(int x)

{

    return x&-x;

}



int sum(int i)

{

    int s=0;

    while(i>0)

    {

        s+=bit[i];

        i-=lb(i);

    }

    return s;

}



void add(int i,int x)

{

    while(i<=maxn)

    {

        bit[i]+=x;

        i+=lb(i);

    }

}



int Che(int x)

{

    memset(bit,0,sizeof(bit));

    memset(ais,0,sizeof(ais));

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

    cnt=0;

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

    {

        cnt+=sum(ais[i]+N);

        add(ais[i]+N,1);

    }

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

}



int Sol()

{

    memcpy(b,a,sizeof(a));

    sort(b+1,b+n+1);

    int l=0,r=n+1,m=(l+r)/2;

    while(l+1<r)

    {

        if(Che(b[m])) l=m;else r=m;

        m=(l+r)/2;

    }

    return b[l];

}



int main()

{

    #ifdef IORD

    freopen("in.txt","r",stdin);

	freopen("out.txt","w",stdout);

	#endif // IORD

    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d",a+i);

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

    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;

}