#include<iostream>

#include<cstdio>

#include<math.h>

#include<algorithm>

#include<map>

#include<set>

#include<bitset>

#include<stack>

#include<queue>

#include<string.h>

#include<string>

#include<cstring>

#include<vector>

#include<time.h>

#include<stdlib.h>

using namespace std;
typedef long long LL;
LL n, l, Min = 1000000005, Max = -1;
LL tot = 0;
LL  a[100005];
LL bit[100005];

void update(LL x,LL val)
{
    x++;
    for(; x< 100005 ;x+=(x & -x))
    {
        bit[x]+=val;
    }
}

LL sum(LL x)
{
    LL ans=0;
    x++;
    for(;x>0;x-=(x & -x))
    {
        ans += bit[x];
    }
    return ans;
}

struct node {
	LL sum, pos;
}arr[100005];


bool cmp(node n1, node n2)
{
	return n1.sum < n2.sum;
}

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].sum = -1;
		else
		arr[i].sum = 1;
		arr[i].pos=i;
    }

        arr[0].sum=0;
        arr[0].pos=0;

		for (int i = 1; i <= n; i++)
			arr[i].sum += arr[i-1].sum;


		sort(arr, arr + n+1, cmp);
        LL ans = 0;
		for (int i = 0; i <= n+1; i++) {
            update(arr[i].pos,1);
			ans += (i-sum(arr[i].pos));
		}

		//cout<<"ans:"<<(ans)<<"--x::"<<x<<endl;
		return ans > tot / 2+1;
}



int main() {

	scanf("%lld", &n);
	tot=0;
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		Min = min(Min, a[i]);
		Max = max(Max, a[i]);
		tot += i;
	}

	LL l = 0, r =Max ;
	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;
}
