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

#include <algorithm>

#include <cstdlib>

#include <iostream>

#include <cmath>

#include <ctime>

#include <cstring>

#define ll long long

#define INF 1000000000

#define For(i,a,b) for(int i=a;i<=b;++i)

#define Rev(i,a,b) for(int i=a;i>=b;--i)

#define pb push_back

#define pq priority_queue

#define PI acos(-1)



namespace IO

{

#define p(x) ('0'<=x&&x<='9')

	char cc; int C;

	template <class T>

	void read( T &x )

	{

		x=0; cc=getchar(); C=1;

		while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

		while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

		x*=C;

	}

#undef p

}



using namespace IO;

using namespace std;



#define N 100005



#define lb(x) (x&-x)

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

ll Arr[N<<1],Arr_minor[N<<1],tot,tot_minor,tot_zero;



ll sigema(int pos)

{

	ll ret=0;

	while(pos)

	{

		ret+=Arr[pos];

		pos-=lb(pos);

	}

	return ret;

}



void add(int pos)

{

	++tot;

	while(pos<=N) ++Arr[pos],pos+=lb(pos);

}



ll sigema_minor(int pos)

{

	ll ret=0;

	while(pos)

	{

		ret+=Arr_minor[pos];

		pos-=lb(pos);

	}

	return ret;

}



void add_minor(int pos)

{

	++tot_minor;

	while(pos<=N) ++Arr_minor[pos],pos+=lb(pos);

}



#undef lb



void init()

{

	read(n);

	For(i,1,n) read(a[i]),b[i]=a[i];

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

}



int main()

{

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);

	srand(time(0));

#ifdef LOCAL

	freopen("./tmp/input.txt", "r", stdin);

#endif

	init();

	int L=1,R=n,mid,pre,ans;

	ll sum;

	const ll total=1LL*n*(n+1)/2;

	const ll target=(total/2)+1;

	while(L<R)

	{

		mid=(L+R)>>1;



		memset(Arr,0,sizeof(Arr)); tot=0;

		memset(Arr_minor,0,sizeof(Arr)); tot_minor=0;

		tot_zero=0;



		For(i,1,n) c[i]=(a[i]<=b[mid]?1:-1);

		sum=pre=0;

		++tot_zero;

		For(i,1,n)

		{

			pre+=c[i];

			if(pre<0)

			{

				sum+=tot_minor;

				sum-=sigema_minor(-pre);

				add_minor(-pre);

				continue;

			}

			if(pre==0)

			{

				sum+=tot_minor;

				++tot_zero;

				continue;

			}

			if(pre>0)

			{

				sum+=tot_minor+tot_zero;

				sum+=sigema(pre-1);

				add(pre);

				continue;

			}

		}

		if(sum>=target) R=mid;

		else L=mid+1;

	}



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



	return 0;

}


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

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef unsigned int uint;

typedef pair<int,int> pii;

const int maxn=1e5+7;

const ll modn=1e9+7;

const int inf=2e9+7;

const ll INF=1000000000000000000ll;

const double PI = acos(-1.0);

const double eps=1e-8;

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

inline ll lowbit(ll x) {return x&-x;}

inline int CountOneBinary(ll num){int ans=0;while(num){if(num&1) ans+=1;num>>=1;}return ans;}

inline void read(int &x){char c;x=0;for(c=getchar();c>'9'||c<'0';c=getchar());for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';}

inline void read(ll &x){char c;x=0;for(c=getchar();c>'9'||c<'0';c=getchar());for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';}

inline ll qpow(ll x,ll y){ll ans=1;while(y){if(y&1) ans=ans*x%modn;x=x*x%modn;y>>=1;}return ans;}

inline double qpow(double x,ll y){double ans=1;while(y){if(y&1) ans=ans*x;x=x*x;y>>=1;}return ans;}

ll n,a[maxn],C[maxn],sum[maxn],stn;

void add(int pos)

{

    for(int i=pos;i<maxn;i+=lowbit(i)) C[i]++;

}

ll query(int pos)

{

    ll ans=0;

    for(int i=pos;i;i-=lowbit(i)) ans+=C[i];

    return ans;

}

bool check(ll x)

{

    memset(C,0,sizeof(C));

    ll bot=1;

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

    {

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

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

        bot=min(sum[i],bot);

    }

    bot-=2;

    ll ans=0;

    add(-bot);

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

    {

        sum[i]-=bot;

        ans+=query(sum[i]);

        add(sum[i]);

    }

    return ans>=stn;

}

int main()

{

    while(scanf("%lld",&n)==1)

    {

        stn=n*(n+1)/2-n*(n+1)/2/2;

        ll l=1e9,r=1;

        for(int i=1;i<=n;i++) scanf("%lld",&a[i]),l=min(a[i],l),r=max(a[i],r);

        while(l<r)

        {

            ll mid=l+(r-l+1)/2;

            if(check(mid))

                l=mid;

            else

                r=mid-1;

        }

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

    }

}


// Fastest known solution for this problem: