#include <vector> // https://atcoder.jp/contests/abc107/submissions/12955333
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


class FenwickTree {
    public:
        FenwickTree(int n) : N(n), data(N, 0) {

        }

        void reset() {
            fill(data.begin(), data.end(), 0);
        }

        void put(int x, int v) {
            for (; x < N; x |= x + 1) {
                data[x] += v;
            }
        }

        int get(int x) {
            int res = 0;
            for (; x >= 0; x = (x & (x + 1)) - 1) {
                res += data[x];
            }
            return res;
        }

    private:
        int N;
        vector<int> data;
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }


    vector<int> B(n, 0);

    int base = -n;

    FenwickTree ft(n * 2 + 123);


    long long tar = n * 1LL * (n + 1) / 2 / 2 + 1;
    // cout << tar << endl;
    auto ok = [&](int x) {
        for (int i = 0; i < n; ++i) {
            if (A[i] <= x) {
                B[i] = 1;
            } else {
                B[i] = -1;
            }
        }
        ft.reset();
        int sum = 0;
        ft.put(sum - base, 1);

        long long res = 0;
        for (auto x : B) {
            sum += x;
            res += ft.get(sum - base - 1);
            ft.put(sum - base, 1);
        }
        return res >= tar;
    };

    int mx = *max_element(A.begin(), A.end());
    long long lo = 0, hi = mx;

    while (lo < hi) {
        auto mi = (lo + hi) >> 1;
        if (ok(mi)) {
            hi = mi;
        } else {
            lo = mi + 1;
        }
    }

    cout << lo << '\n';

    return 0;
}