#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N = 3e5 + 100;
int Mx;
int n, a[N], v[N], c[N];
int t[N << 1];
int lowbit(int x){return x & -x;}
void init(){memset(t, 0, sizeof(t));}
void add(int x){for(;x <= Mx;x += lowbit(x)) t[x]++;}
ll qry(int x){ll r = 0;for(;x;x -= lowbit(x)) r += t[x];return r;}
ll ned;
bool chk(int val){
    int s = n + 1;ll cnt = 0;
    init();add(s);
    for(int i = 1;i <= n;i++){
        s += (a[i] <= val) ? 1 : -1;
        cnt += qry(s); 
        add(s);
    }
    return cnt >= ned;
}
int32_t main(){
    cin >> n;
    ned = (1ll * n * (n + 1) / 2 + 1) / 2;Mx = 2 * (n + 1);
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        v[i] = a[i];
    }
    sort(v + 1, v + 1 + n);
    int lft = 1, rit = n, ans = -1;
    while(lft <= rit){
        int mid = (lft + rit) >> 1;
        if(chk(v[mid])) ans = v[mid], rit = mid - 1;
        else lft = mid + 1;
    }
    cout << ans << endl;
    return 0;
}