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