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

using namespace std;



const int maxn = 1e5+10;

int a[maxn];

int b[maxn];

int n;



int c[maxn],tmp[maxn];

long long ans;



void Merge(int l,int m,int r)

{

    int i = l;

    int j = m + 1;

    int k = l;

    while(i <= m && j <= r)

    {

        if(c[i] > c[j])

        {

            tmp[k++] = c[j++];

            ans += m - i + 1;

        }

        else

        {

            tmp[k++] = c[i++];

        }

    }

       while(i <= m) tmp[k++] = c[i++];

    while(j <= r) tmp[k++] = c[j++];

    for(int i=l;i<=r;i++)

        c[i] = tmp[i];

}

 

void Merge_sort(int l,int r)

{

    if(l < r)

    {

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

        Merge_sort(l,m);

        Merge_sort(m+1,r);

        Merge(l,m,r);

    }

}



int lowbit(int x){

    return x&(-x);

}



void add(int x,int d){

    while(x<=n){

        b[x]+=d;

        x+=lowbit(x);

    }

}





int sum(int x){

    int res = 0;

    while(x){

        res+=b[x];

        x-=lowbit(x);

    }

    return res;

}



bool cc(int d){

    memset(b,0,sizeof(b));

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

    if(a[i]>=d)add(i,1);

    else add(i,-1);

}

    for(int i=1;i<=n;i++)c[i] = sum(i);

        ans = 0;

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

            if(c[i]<0)ans++;//单个前缀和小于0

        }

        Merge_sort(1,n);//统计逆序数

        long long num = 1LL*n*(n+1)/2 - ans;

        return num>=ans;

}



int main(){

    scanf("%d",&n);

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

    int ub = 1e9;

    int lb = 0;

        while(ub-lb>1){

            int mid = lb+(ub-lb)/2;

            if(cc(mid))lb = mid;

            else ub = mid;

        }

        if(cc(lb+1))lb++;

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

    return 0;

}

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

#include<algorithm>

using namespace std;

const int MAXN = 100000;

const int INF = int(1E9);

int arr[MAXN + 5], sum[MAXN + 5], temp[MAXN + 5];

long long tot1 = 0, tot2 = 0;

int N;

void MergeSort(int le, int ri) {

    if( le == ri ) return ;

    int mid = (le + ri) >> 1;

    MergeSort(le, mid);

    MergeSort(mid+1, ri);

    int p = le, q = mid+1, r = le;

    while( p <= mid && q <= ri ) {

        if( sum[p] < sum[q] ) {

            temp[r++] = sum[p++];

        }

        else {

            tot1 += (p-le);

            temp[r++] = sum[q++];

        }

    }

    while( p <= mid ) {

        temp[r++] = sum[p++];

    }

    while( q <= ri ) {

        tot1 += (p-le);

        temp[r++] = sum[q++];

    }

    for(int i=le;i<=ri;i++)

        sum[i] = temp[i];

}

bool Check(int x) {

    tot1 = 0;

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

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

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

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

    MergeSort(0, N);

    return tot1 >= (tot2/2 + 1);

}

int main() {

    int le = INF, ri = -INF;

    scanf("%d", &N);

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

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

        le = min(le, arr[i]);

        ri = max(ri, arr[i]);

        tot2 += i;

    }

    while( le < ri ) {

        int mid = (le + ri) >> 1;

        if( Check(mid) ) ri = mid;

        else le = mid + 1;

    }

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

}

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

}