#include <bits/stdc++.h>
using namespace std;

#define int long long
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;
constexpr int MOD = 1e9 + 7;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vec>;

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << " " << p.second;
}
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}
template <typename T>
T sum_(vector<T> vec, T init = 0) {
    return std::accumulate(all(vec), T(init));
}

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

template <typename T>
void init(vector<T>& v) {
    rep (i, v.size())
        cin >> v[i];
}

template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) {
    assert(v.size() == w.size());
    rep (i, v.size())
        cin >> v[i] >> w[i];
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

// -------------------------------------------------------------------
// sort 1 2 3 4

class BIT {
    // ATTENTION: this tree is one-indexed
    std::vector<int> tree;
    int MAX_SIZE;

public:
    BIT(int max) : tree(max), MAX_SIZE(max) {}
    void add(int idx, int val) {
        for (int x = idx; x < MAX_SIZE; x += x & -x) tree[x] += val;
    }
    int sum(int idx) {
        int ret = 0;
        for (int x = idx; x > 0; x -= x & -x) ret += tree[x];
        return ret;
    }
};

int n;
int thre;

bool tf(vec a, int val) {
    vec v(n);
    rep (i, n)
        v[i] = (a[i] >= val) ? 1 : -1;

    For(i, 1, n - 1) v[i] = v[i - 1] + v[i];

    BIT bit(n * 4 + 1);
    int res = 0;
    bit.add(n * 2, 1);
    rep (i, n) {
        res += bit.sum(v[i] + n * 2);
        bit.add(v[i] + n * 2, 1);
    }
    return res >= thre;
}

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    cin >> n;
    vec a(n);
    init(a);
    thre = n * (n - 1) / 2 + n + 1;
    thre /= 2;

    int upp = 1e9 + 1, low = 0;
    while (upp - low > 1) {
        int mid = (upp + low) / 2;
        bool res = tf(a, mid);
        if (res)
            low = mid;
        else
            upp = mid;

        if (upp - low == 1) break;
    }
    print(low);

    return 0;
}


Measured memory_bytes: 5760