// Slower C++ solution:
//404 Not Found {=}7 (o)7 (x)7

#include<bits/stdc++.h>

using namespace std;

#define append push_back

#define endl "\n"

#define dbug(x) cout<<#x<<"="<<x<<endl



typedef long long int ll;

typedef long double ld;

typedef pair<int,int> pii;



const ll maxn = 5e5+10, inf = 1e9, mod= 1e9+7;

ll a[maxn];

vector<ll> v;

ll b[maxn];

ll fen[maxn+10];

ll par[maxn];

ll get(ll id)

{

    ll sum = 0;

    for(;id;id -= id&-id)

        sum += fen[id];

    return sum;

}

void add(ll id)

{

    for(;id<maxn;id += id&-id)

        fen[id] ++;

}

int main(){

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    

    ll n;

    cin >> n;

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

        cin >> a[i];

        v.append(a[i]);

    }

    sort(v.begin(),v.end());

    ll l=0,r=n;

    while(l+1 < r)

    {

        ll mid = (l+r) / 2;

        

        for(ll i = 0;i<n;i++)

            b[i] = (a[i]<v[mid]?1ll:-1ll);

        b[0] += n+2;

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

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



        ll ans = 0;

        add(n+2);

        ans += get(b[0]-1);

        add(b[0]);

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

        {

            ans += get(b[i]-1);

            add(b[i]);

        }                                   

        if(ans > (n*(n+1))/4)

        {

            r = mid;

        }

        else

        {

            l = mid;

        }

        for(ll i = 0;i<maxn;i++)

            fen[i] =0;

    }

    cout << v[l];

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 9.175361824006671x):
#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;

}