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

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<iostream>

using namespace std;

#define ll long long

#define REP(a,b,c) for(int a=b;a<=c;a++)

#define re register

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

typedef pair<int,int> pii;

#define mp make_pair

inline int gi()

{

	int f=1,sum=0;char ch=getchar();

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

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

const int N=100010;

int n,a[N],o[N],v[N],c[N<<1],s[N];

ll all;

int lowbit(int x){return x&(-x);}

void Add(int x,int d){while(x<=(n<<1)){c[x]+=d;x+=lowbit(x);}}

int query(int x){int ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret;}

bool check(int mid)

{

	for(int i=1;i<=n;i++)v[i]=(a[i]>=o[mid])?1:-1;

	ll ret=0;

	for(int i=1;i<=n;i++)s[i]=s[i-1]+v[i],ret+=(s[i]<0);

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

	for(int i=n;i;i--)

	{

		ret+=query(s[i]+n-1);

		Add(s[i]+n,1);

	}

	return ret*2<=all;

}

int main()

{

	n=gi();all=1ll*n*(n+1)/2;

	for(int i=1;i<=n;i++)a[i]=o[i]=gi();sort(o+1,o+n+1);int tot=unique(o+1,o+n+1)-o-1;

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

	while(l<=r)

	{

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

		if(check(mid)){ans=mid;l=mid+1;}

		else r=mid-1;

	}

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

	return 0;

}


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



using namespace std;

#define int long long

#define x first

#define y second



#define vert int v, int tl, int tr

#define tm ((tl + tr) >> 1)

#define left (v << 1), tl, tm

#define right (v << 1) + 1, tm, tr



typedef pair<int, int> pii;

typedef long long ll;

typedef long double ld;



int n;

int a[100009];

int pref[100009];



int tree[800009];

void build(vert) {

    tree[v] = 0;

    if (tr - tl == 1) return;



    build(left);

    build(right);

}



void upd(vert, int i, int x) {

    tree[v] += x;

    if (tr - tl == 1) {

        return;

    }



    if (i < tm) {

        upd(left, i, x);

    }



    else {

        upd(right, i, x);

    }

}



int getsum(vert, int l, int r) {

    if (l >= tr || tl >= r) return 0;

    if (tl >= l && tr <= r) return tree[v];

    return getsum(left, l, r) + getsum(right, l, r);

}



int check(int x) {

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

        if (a[i] >= x)

            pref[i + 1] = pref[i] + 1;

        else

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

    }



    build(1, 0, 2 * n + 2);

    int cnt = 0;

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

        cnt += getsum(1, 0, 2 * n + 2, 0, pref[i] + n + 1);

        upd(1, 0, 2 * n + 2, pref[i] + n, 1);

    }



    return cnt;

}



signed main() {

    ios :: sync_with_stdio(0);

    cin.tie(0);



    cin >> n;

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

        cin >> a[i];

    }



    int l = 0, r = (1e9) + 1;

    int eth = (n * n) / 2;

    while (r - l > 1) {

        int m = (r + l) / 2;

        if (check(m) <= (eth + 1) / 2) {

            r = m;

        }



        else {

            l = m;

        }

    }



    cout << l;



    return 0;

}


// Fastest known solution for this problem: