#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long 
using namespace std;
const ll INF = 1e18+10;
const int N = 1e5+10;
ll n, a[N];
ll l, r, mid, ans, sum[N], tmp[N];
ll lim;
 
 
void chkMin(ll &x, ll y){if (x > y) x = y;}
void chkMax(ll &x, ll y){if (x < y) x = y;}
 
ll Msort(ll le, ll ri)//计算中位数大于等于mid的[l, r]对数，具体过程类似逆序对
{
    if (le == ri)
        return 0;
    ll mid = (le+ri)>>1;
    ll ret = 0;
    ret += Msort(le, mid);
    ret += Msort(mid+1, ri);
    ll i = le, j = mid+1, k = le;
    while (i <= mid && j <= ri){
        if (sum[i] <= sum[j]){
            tmp[k++] = sum[i++];
            ret += ri-j+1;
        }
        else
            tmp[k++] = sum[j++];
    }
    while (i <= mid)
        tmp[k++] = sum[i++];
    while (j <= ri)
        tmp[k++] = sum[j++];
    for (ll o = le; o <= ri; o++)
        sum[o] = tmp[o];
    return ret;
}
 
bool Check(ll mid)
{
    sum[0] = 0;
    for (ll i = 1; i <= n; i++){
        sum[i] = sum[i-1];
        if (a[i] >= mid) sum[i]++;
        else sum[i]--;
    }
    if (Msort(0, n) >= lim) return true;
    return false;
}
 
int main()
{
    cin >> n;
    lim = (n*(n-1)/2+n+1)/2;//中位数大于等于median of medians的区间个数下界
    l = INF; r = -INF;
    for (ll i = 1; i <= n; i++){
        cin >> a[i];
        chkMin(l, a[i]);
        chkMax(r, a[i]);
    }
    while (l <= r){
        mid = (l+r)>>1;
        if (Check(mid))
            ans = mid, l = mid+1;
        else
            r = mid-1;
    }
    cout << ans;
    return 0;
}