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

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <queue>

#include <vector>

#include <map>

#define mem(u, v) memset(u, v, sizeof(u))

#define INF 0x3f3f3f3f

#define pii pair<int, int >

#define LL long long

#define mid (l + r) / 2

#define lowbit(x) x & -x

using namespace std;

const int MAXN = 1e6 + 7,  MAXM = 1e6 + 7, MAXK = 1e6 + 7;



int a[MAXN], b[MAXN], sum[MAXN], c[MAXN], n;

LL ans0;



void add(int x){

	while (x <= 5 * n){

		c[x] += 1;

		x += lowbit(x);

	}

}



int get(int x){

	int y = 0;

	while (x > 0){

		y += c[x];

		x -= lowbit(x);

	}

	return y;

}



bool judge(int x){

	sum[0] = 0;

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

		if (a[i] >= x) sum[i] = sum[i - 1] + 1;

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

	}

	for (int i = 0; i <= n; i++) sum[i] = 2 * sum[i] - i + n + 1;

	LL ans1 = 0;

	mem(c, 0);

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

		ans1 += get(sum[i]);

		add(sum[i]);

	}

	if (ans1 >= ans0) return true;

	return false;

}



int main(){

	scanf("%d", &n);

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

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

	int l = 1, r = n, ans = 0;

	ans0 = (1LL * n * (n - 1) / 2 + n + 1) / 2LL;

	while (l <= r){

		if (judge(b[mid])) ans = mid, l = mid + 1;

		else r = mid - 1;

	}

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

	return 0;

}


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

#include<cstdio>

#include<math.h>

#include<algorithm>

#include<map>

#include<set>

#include<bitset>

#include<stack>

#include<queue>

#include<string>

#include<cstring>





using namespace std;

typedef long long LL;

const int maxn=1e6+7;

LL n;

LL tot=0;

LL mn=0x3f,mx=-0x3f;

LL a[maxn];

LL bit[maxn];



struct node {

LL val,pos;

}arr[maxn];



bool cmp(node n1,node n2)

{

    return n1.val==n2.val?n1.pos<n2.pos:n1.val<n2.val;

}



void update(LL x,LL val)

{

    for(; x< maxn ;x+=(x & -x))

    {

        bit[x]+=val;

    }

}



LL getsum(LL x)

{

    LL ans=0;

    for(;x>0;x-=(x & -x))

    {

        ans += bit[x];

    }

    return ans;

}







bool check(LL x){

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

     memset(arr,0,sizeof(arr));





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

    {

        if(a[i]<=x)arr[i].val=-1;

        else arr[i].val=1;

        arr[i].pos=i+1;

    }



    arr[0].val=-1;

	arr[0].pos=1;



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

	arr[i].val+=arr[i-1].val;

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



	LL ans=0;

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

    {

        ans+=(i-getsum(arr[i].pos));

        update(arr[i].pos,1);

    }

	return ans*2 > tot;

}





int main(){

   scanf("%lld",&n);



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

    {

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

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

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

   	 tot+=i;

   }



   LL l=mn,r=mx;

   while(r-l>1)

    {

   	  LL mid=(l+r)/2;

   	 if(check(mid)) r=mid;

   	 else l=mid;

   	 //printf("s%d",mid);

   }

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



   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;

}