#include <bits/stdc++.h>

#ifndef ONLINE_JUDGE
#define gc getchar
#define pc putchar
#else
#define gc getchar_unlocked
#define pc putchar_unlocked
#endif

using namespace std;

#define vi vector<int>
#define si set<int>
#define vs vector<string>
#define pii pair<int,int>
#define vpi vector<pii>
#define pri priority_queue<int>
#define rev_pri priority_queue<int,vector<int>,greater<int> >
#define mpi map<int,int>
#define i64 long long int
#define endl '\n'
#define pi acos(-1)
#define all(v) v.begin(),v.end()
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf INT_MAX/2
#define infll LLONG_MAX/3
#define For(i,n) for(int i=0;i<n;i++)
#define Fre(i,a,b) for(int i = a; i < b; i++)
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pfn(n) printf("%d\n", n)
#define pfs(n) printf("%d ", n)
#define eps 1e-8
#define ff first
#define ss second
#define mem(a,b) memset(a,b,sizeof(a))
#define READ freopen("in.txt", "r", stdin)
#define WRITE freopen("out.txt", "w", stdout)
#define sz size()
#define dbg(i) printf("yo %d\n", i)
#define foreach(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define sqr(a) (a) * (a)
#define clr clear()
#define CASE(a) printf("Case %d: ",a)

//int dx[] = {0,1,0,-1,1,1,-1,-1};
//int dy[] = {1,0,-1,0,1,-1,-1,1};


//i64 gcd(i64 a,i64 b){if(!b)return a;return gcd(b,a%b);}

//inline void fastRead(int *a){register char c=0;while(c<33)c=gc();*a=0;while(c>33){*a=*a*10+c-'0';c=gc();}}

//inline void fastWrite(int a){char snum[20];int i=0;do{snum[i++]=a%10+48;a=a/10;}while(a!=0);i=i-1;while(i>=0)pc(snum[i--]);pc('\n');}

//i64 bigmod(i64 num,i64 n){if(n==0)return 1;i64 x=bigmod(num,n/2);x=x*x%mod;if(n%2==1)x=x*num%mod;return x;}

//i64 modinverse(i64 num){return bigmod(num,mod-2)%mod;}

//i64 po(i64 a,i64 b){i64 ans=1;while(b--)ans *= a;return ans;}

//i64 ncr(i64 n,i64 r){if(n==r)return 1;if(r==1)return n;if(dp[n][r]!=-1)return dp[n][r];return dp[n][r]=ncr(n-1,r)+ncr(n-1,r-1);}


// bit manipulations

//bool checkbit(int mask,int bit){return mask & (1<<bit);}

//int setbit(int mask,int bit){ return mask  (1<<bit) ; }

//int clearbit(int mask,int bit){return mask & ~(1<<bit);}

//int togglebit(int mask,int bit){return mask ^ (1<<bit);}

#define mxn 100015

vi v;
vi w;

int tem[mxn];
i64 BIT[mxn * 2];

void update(int idx, int val)
{
	idx += mxn;
	for( ; idx < mxn * 2; idx += idx&(-idx))
		BIT[idx] += val;
}

int query(int idx)
{
	idx += mxn;
	int sum = 0;
	for( ; idx > 0; idx -= idx & (-idx))
		sum += BIT[idx];

	return sum;
}

i64 tot;


/// Learnt from https://codeforces.com/blog/entry/18879
/// Gives us number of continuous subseq. (median greater than x)

i64 f(int x)
{
	For(i,w.sz)
                if(w[i]>=x)
                        tem[i] = 1;
                else
                        tem[i] = -1;

	mem(BIT,0);
	update(0,1);
        i64 sum = 0;
        i64 ans = 0;
	For(i,v.sz)
	{
                sum += tem[i];
                ans += query(sum);
                update(sum,1);
	}

        i64 st = tot - ans ;
//        cout << x << " " << tot << " " << ans << endl;
        return st;
}


int main()
{
	int n,inp;
	sf(n);
	For(i,n)
	{
		sf(inp);
		v.pb(inp);
	}
        w = v;

        sort(all(v));

//        For(i,v.sz)
//                cout << v[i] << " ";
//        cout << endl;

	tot = v.sz * (v.sz+1 ) /2;
	i64 medPos = tot / 2;

	int lo = 0, hi = v.sz - 1, ans;

//        cout << medPos << endl;

	while(lo<=hi)
	{
	        int mid = (lo+hi)/2;

//	        cout << mid << " " << f(v[mid]) << endl;
//                cout << lo << " " << hi << endl;
		if(f(v[mid])<=medPos)
		{
			lo = mid + 1;
			ans = mid;
		}
		else
			hi = mid - 1;
	}


        cout << v[ans] << endl;











	return 0;
}




Measured memory_bytes: 3064