#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
struct BIT {
    long long n = 600000, t[600010];
    void modify(long long k, long long x) {
        k += 300000;
        for (long long i = k; i <= n; i += i & (-i)) {
            t[i] += x;
        }
    }
    long long query(long long k) {
        k += 300000;
        long long ans = 0;
        for (long long i = k; i >= 1; i -= i & (-i)) {
            ans += t[i];
        }
        return ans;
    }
} bt;
long long n, a[300010], b[300010], s[300010];
long long solve(long long x) {
    for (long long i = 1; i <= n; i++) {
        if (a[i] <= x) {
            b[i] = -1;
        } else {
            b[i] = 1;
        }
    }
    memset(bt.t, 0, sizeof(bt.t));
    bt.modify(0, 1);
    long long res = 0;
    for (long long i = 1; i <= n; i++) {
        b[i] += b[i - 1];
        res += i - bt.query(b[i] - 1);
        bt.modify(b[i], 1);
    }
    return res;
}
int main() {
    scanf("%lld", &n);
    for (long long i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        s[i] = a[i];
    }
    sort(s + 1, s + n + 1);
    long long all = n * (n + 1) / 2;
    long long tot = n * (n + 1) / 2 / 2 + 1;
    long long l = 1, r = n, ans = 0;
    while (l <= r) {
        long long mid = (l + r) >> 1;
        long long ck = solve(s[mid]);
        if (ck >= tot) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    printf("%lld\n", s[ans]);
    return 0;
}