#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>
#include <complex>
#include <functional>
#include <tuple>

using namespace std;

#define Rep(i,a,b) for(ll i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")

using ll = long long;

constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

namespace {
    template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
    template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }
    template<typename T> void chadd(T& a, T b) { a = a + b; }

    void Cout(long long x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const T& x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cout << x[i] << (i == sz - 1 ? end : sep); } }

    // 標準入出力
    struct inp {
        std::size_t sz;
        inp(std::size_t _sz = 1) : sz(_sz) {}
        template <typename T> operator T () const { T a; std::cin >> a; return a; }
        template <typename T> operator std::vector<T>() const { std::vector<T> a(sz); for (std::size_t i = 0; i < sz; i++) std::cin >> a[i]; return a; }
    };

    // 2次元用の標準入出力
    template<typename T>
    struct inpn {
        std::size_t szi, szj;
        inpn(std::size_t _szi, std::size_t _szj) : szi(_szi), szj(_szj) {}
        operator std::vector<std::vector<T>>() const {
            std::vector<std::vector<T>> a(szi, std::vector<T>(szj));
            for (std::size_t i = 0; i < szi; ++i)
                for (std::size_t j = 0; j < szj; ++j) cin >> a[i][j];
            return a;
        }
    };

    inp inp1; // input one

        // セグメントツリーのライブラリ
    template<typename T>
    class SegmentTree {
    public:
        // _n:必要サイズ, _def:初期値かつ単位元, _operation:クエリ関数,
        // _update:更新関数
        SegmentTree(size_t _n, T _def, std::function<T(T, T)> _operation,
            std::function<T(T, T)> _update)
            : def(_def), operation(_operation), update(_update) {
            n = 1;
            while (n < _n) {
                n *= 2;
            }
            node = std::vector<T>(2 * n - 1, def);
        }

        // 場所i(0-indexed)の値をxで更新
        void change(int i, T x) {
            i += n - 1;
            node[i] = update(node[i], x);
            while (i > 0) {
                i = (i - 1) / 2;
                node[i] = operation(node[i * 2 + 1], node[i * 2 + 2]);
            }
        }

        // [a, b)の区間クエリを実行
        T query(int a, int b) {
            return _query(a, b, 0, 0, n);
        }

        // 添字でアクセス
        T operator[](int i) {
            return node[i + n - 1];
        }

        int n;                       // 葉の数
        std::vector<T> node;              // データを格納するvector
    private:
        T def;                       // 初期値かつ単位元
        std::function<T(T, T)> operation; // 区間クエリで使う処理
        std::function<T(T, T)> update;    // 点更新で使う処理

        // 区間[a,b)の総和。ノードk=[l,r)に着目している。
        T _query(int a, int b, int k, int l, int r) {
            if (r <= a || b <= l) return def; // 交差しない
            if (a <= l && r <= b)
                return node[k]; // a,l,r,bの順で完全に含まれる
            else {
                T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子
                T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子
                return operation(c1, c2);
            }
        }
    };
}

int main() {

    ll n = inp1;
    vector<ll> a = inp(n);

    ll ans = 0LL;
    ll sz = (n + 1) * n / 2;
    // 二分探索
    // 全区間を見て，ans以下のものが半分(奇:sz/2+1, 偶:sz/2+1)を占めるかどうか
    ll half = sz / 2 + 1LL;
    //Cout(half);

    // 上の判定をO(n)でやりたい

    // 置き換え
    // ans以下のものに-1を
    // ansより大きいものに1を置く
    // 区間の総和が負になるものはただしい

    // ただしいものが half以上になるかどうか

    ll mi = -n * 2;
    SegmentTree<int> seg(-mi + n, 0, [](int a, int b)->int {return a + b; }, [](int a, int b)->int {return a + b; });

    int left = 0; int right = 1e9 + 1;
    while (right - left > 1) {
        int mid = (right + left) / 2;

        // 置き換える
        vector<ll> ta(n);
        rep(i, n) {
            if (a[i] <= mid) ta[i] = -1;
            else ta[i] = 1;
        }

        vector<ll> sum(n + 1, 0LL);
        rep(i, n) {
            sum[i + 1] = sum[i] + ta[i];
        }

        // [i, j) において，
        // s[j] - s[i] < 0　なら正しい
        // s[i] > s[j]　となる場合の数を求める 転倒数と同じ考え
        // s[i]を見るとき，右側に地震より小さい値がいくつあるか
        ll num = 0LL;
        for (int i = n; i >= 0; --i) {
            num += seg.query(0, -mi + sum[i]);
            seg.change(-mi + sum[i], +1);
        }
        // 終わったので戻す
        rep(i, n + 1) seg.change(-mi + sum[i], -1);

        //cout << "mid : " << mid << " " << num << endl;

        if (num >= half) {
            right = mid;
        }
        else left = mid;
    }

    ans = left + 1;

    // 2分探索，簡単なアルゴリズムなのに見えづらくてかなり良い
    Cout(ans);

    // 計算量 O(nlognlog(1e9)) 危なさそう

    return 0;
}


Measured memory_bytes: 6748