#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath> // 変数名にy1が使えなくなるかも…。
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <limits>
#include <string>

typedef __int128_t int128_t;
std::istream &operator>>(std::istream& input, int128_t& value) { // int128_tの入力。入力が64bitに収まる前提。
    long long tmp; input >> tmp; value = tmp;
    return input;
}
std::ostream &operator<<(std::ostream& output, const int128_t value) { // int128_tの出力。出力が64bitに収まる前提。
    output << (long long)value;
    return output;
}

// binary search result
struct BSR {
    bool found; // 条件を満たす範囲が見つかったか。falseの場合、begin,endは意味を持たない。
    int128_t begin; // [begin, end]で条件が成り立つ。
    int128_t end;

    BSR(bool found_in, int128_t begin_in, int128_t end_in) : found(found_in), begin(begin_in), end(end_in) {}
};

template<class Fn> BSR binary_search(int128_t L, int128_t R, Fn func) {
    const bool res_L = func(L);
    const bool res_R = func(R);
    if (res_L && res_R) {
        return BSR(true, L, R);
    } else if (!res_L && !res_R) {
        return BSR(false, 0, 0);
    } else {
        int128_t lb = L;
        int128_t ub = R;
        while (lb + 1 < ub) {
            int128_t mid = (lb + ub) / 2;
            if (res_L == func(mid)) {
                lb = mid;
            } else {
                ub = mid;
            }
        }
        if (res_L) {
            return BSR(true, L, lb);
        } else {
            return BSR(true, ub, R);
        }
    }
}

template<typename T>
//std::map<T, int> coordinate_compress(const std::vector<T>& vec, const bool reverse = false) {
std::unordered_map<T, int> coordinate_compress(const std::vector<T>& vec, const bool reverse = false) {
    // 座標圧縮。要素の小さい順に1-indexで値を割り振る。
    // reverse = trueの場合、大きい順に割り当てるが、mapでの保存順序は常に小さい順である。
    // Tに順序が設定されていればよいので、時間制限の問題が無ければunordered_mapより広い範囲で使える。
    // auto compress = coordinate_compress<T>(...) で利用可能。
    std::vector<T> tmp = vec;
    std::sort(tmp.begin(), tmp.end());
    tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
    //std::map<T, int> mp;
    std::unordered_map<T, int> mp;
    for (int i = 0; i < tmp.size(); i++) {
        mp[tmp[i]] = reverse ? tmp.size() - i : i + 1;
    }
    return mp;
}

template<typename T>
//std::map<T, int> coordinate_compress(const T* A, const int L, const int R, const bool reverse = false) {
std::unordered_map<T, int> coordinate_compress(const T* A, const int L, const int R, const bool reverse = false) {
    std::vector<T> vec;
    for (int i = L; i <= R; i++) {
        vec.push_back(A[i]);
    }
    return coordinate_compress(vec, reverse);
}

template<typename T>
//std::vector<T> coordinate_expand(const std::map<T, int>& mp) {
std::vector<T> coordinate_expand(const std::unordered_map<T, int>& mp) {
    // 座標展開。coordinate_compressで圧縮した座標を元の値に戻すための配列を与える。
    // auto expand = coordinate_expand<T>(mp) で利用可能。
    std::vector<T> ret; ret.resize(mp.size()+1);
    for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
        assert(itr->second < ret.size());
        ret[itr->second] = itr->first;
    }
    return ret;
}

// range_query
enum RQ_type {
    MAX_MAX, // 更新クエリ: i:[l, r]に対して、x[i] = max(x[i], o). 求値クエリ: i:[l, r]に対して max(x[l],...,x[r]).
    MIN_MIN, // 更新クエリ: i:[l, r]に対して、x[i] = min(x[i], o). 求値クエリ: i:[l, r]に対して min(x[l],...,x[r]).
    ADD_MAX, // 更新クエリ: i:[l, r]に対して、x[i] += o.           求値クエリ: i:[l, r]に対して max(x[l],...,x[r]).
    ADD_MIN, // 更新クエリ: i:[l, r]に対して、x[i] += o.           求値クエリ: i:[l, r]に対して min(x[l],...,x[r]).
    SUB_MAX, // 更新クエリ: i:[l, r]に対して、x[i] = o.            求値クエリ: i:[l, r]に対して max(x[l],...,x[r]).
    SUB_MIN, // 更新クエリ: i:[l, r]に対して、x[i] = o.            求値クエリ: i:[l, r]に対して min(x[l],...,x[r]).
    ADD_SUM, // 更新クエリ: i:[l, r]に対して、x[i] += o.           求値クエリ: i:[l, r]に対して sum(x[l],...,x[r]).
    MANUAL, // 手動で任意のものを与える場合。
};

template <RQ_type rqt>
class RQ {
    public:

    int n;
    std::vector<int128_t> data, lazy;
    RQ() {}
    RQ(const int size) {
        // 要素数を2のべき乗にする。
        // kの子をk*2+1,k*2+2とするやり方は、0-index配列に準拠している。1-indexの配列に適用することも考えて、
        // x[0]...x[size]が問題なく確保出来るよう、nはsize+1以上の2冪にする。
        n = 1;
        while (n < size + 1) {
            n *= 2;
        }
        data.resize(n*2, id_val());
        lazy.resize(n*2, id_op());
    }

    // 全てを初期値に戻す。セグメント木を何度も利用する場合に用いる。
    void reset() {
        for (int i = 0; i < data.size(); i++) {
            data[i] = id_val(); lazy[i] = id_op();
        }
    }

    // 求値クエリに寄与しない値。
    // op1(v, id_val()) = op1(id_val(), v) = v となるもの。
    int128_t id_val() {
        switch(rqt) {
            case MAX_MAX:
            case ADD_MAX:
            case SUB_MAX:
                return std::numeric_limits<int64_t>::min();
                // データをint128_tとしているのは、modの取り忘れ等でオーバーフローしないためであり、最大値最小値などは64bitに収まる想定。
                // std::numeric_limits<int128_t>は出力が未定義で適切に存在するのか不明なので使わない。
                // 最小値として別の値(0など)を用いるべきケースでは、適切に初期化クエリを行うこと。
                // 加算クエリなら update(1, N, -rq.id_val())、それ以外なら update(1, N, 0)とすれば、[1,N]を0にできる。
            case MIN_MIN:
            case ADD_MIN:
            case SUB_MIN:
                return std::numeric_limits<int64_t>::max();
            case ADD_SUM:
                return 0;
            case MANUAL:
                assert(false);
                return 0;
        }
    }

    // 更新操作の単位元。何も更新しない操作。
    // op2(v, id_op()) = v, op3(o, id_op()) = op3(id_op(), o) = o となるもの。
    int128_t id_op() {
        switch(rqt) {
            case MAX_MAX:
            case SUB_MIN:
            case SUB_MAX:
                return std::numeric_limits<int64_t>::min();
                // 更新操作が代入の場合、正しくは単位元のフラグが必要だが、int64_tの最小値をフラグ代わりに利用する。
                // 実際に数列の値をint64_tの最小値にすることは論理的にできなくなることに注意。
            case MIN_MIN:
                return std::numeric_limits<int64_t>::max();
            case ADD_MAX:
            case ADD_MIN:
            case ADD_SUM:
                return 0;
            case MANUAL:
                assert(false);
                return 0;
        }
    }

    // 求値クエリにおいて、2つの値を1つの値に結合する演算。
    int128_t op1(int128_t v1, int128_t v2) {
        switch(rqt) {
            case MAX_MAX:
            case ADD_MAX:
            case SUB_MAX:
                return std::max(v1, v2);
            case MIN_MIN:
            case ADD_MIN:
            case SUB_MIN:
                return std::min(v1, v2);
            case ADD_SUM:
                return v1 + v2;
            case MANUAL:
                assert(false);
                return 0;
        }
    }

    // 更新操作。以下の2つの条件のうち、どちらかが成り立つ必要がある。
    // 条件1: 2つの値を結合してから更新操作した値と、2つの値に更新操作してから結合した値が等しい。すなわち
    // op2(op1(v1, v2), o) = op1(op2(v1, o), op2(v2, o))
    // 条件2: 2つの値を結合してから、2倍の更新操作をした値と、2つの値に更新操作してから結合した値が等しい。すなわち
    // op2(op1(v1, v2), o*2) = op1(op2(v1, o), op2(v2, o))
    // 条件2を満たす場合、各ノードでの更新は、対応する区間長さを係数とする操作を行う。
    int128_t op2(int128_t v, int128_t o, const int l, const int r) {
        switch(rqt) {
            case MAX_MAX:
                return std::max(v, o);
            case MIN_MIN:
                return std::min(v, o);
            case ADD_MAX:
            case ADD_MIN:
                return v + o;
            case SUB_MAX:
            case SUB_MIN:
                return o == id_op() ? v : o;
            case ADD_SUM:
                return v + o * (r - l);
            case MANUAL:
                assert(false);
                return 0;
        }
    }

    // 更新操作のマージ
    // 2つの更新操作を2度行った結果と、2つの更新操作を1つにまとめた更新操作を1度行った結果が等しくなる必要がある。すなわち
    // op2(op2(v, o1), o2) = op2(v, op3(o1, o2)) 
    int128_t op3(int128_t o1, int128_t o2) {
        switch(rqt) {
            case MAX_MAX:
                return std::max(o1, o2);
            case MIN_MIN:
                return std::min(o1, o2);
            case ADD_MAX:
            case ADD_MIN:
            case ADD_SUM:
                return o1 + o2;
            case SUB_MAX:
            case SUB_MIN:
                return o2 == id_op() ? o1 : o2;
            case MANUAL:
                assert(false);
                return 0;
        }
    }

    void push(const int k, const int l, const int r) { // node に対して、lazyの操作を行い、子のノードに伝播する。lazy[k]は単位元に戻す。
        if (lazy[k] == id_op()) { return; }
        if (k < n - 1) {
            lazy[k*2 + 1] = op3(lazy[k*2 + 1], lazy[k]);
            lazy[k*2 + 2] = op3(lazy[k*2 + 2], lazy[k]);
        }
        data[k] = op2(data[k], lazy[k], l, r);
        lazy[k] = id_op();
    }

    // データ配列の区間[a,b)の連結値を求める。
    // k:探索しているセグメント木の節点のセグメント木配列番号
    // [l, r):kに対応する区間
    int128_t query_child(const int a, const int b, const int k, const int l, const int r) {
        if (r <= a || b <= l) { return id_val(); }
        if (a <= l && r <= b) { return op2(data[k], lazy[k], l, r); }
        push(k, l, r);

        int128_t vl = query_child(a, b, k*2 + 1, l, (l+r)/2);
        int128_t vr = query_child(a, b, k*2 + 2, (l+r)/2, r);
        return op1(vl, vr);
    }

    // データ配列の区間[a,b]の連結値を求める。query_childと異なり閉区間
    int128_t query(const int a, const int b) {
        return query_child(a, b+1, 0, 0, n);
    }

    // [a, b)の区間に、oで表される演算を行う。
    // k:探索しているセグメント木の節点のセグメント木配列番号
    // [l, r):kに対応する区間
    void update_child(const int a, const int b, const int k, const int l, const int r, int128_t o) {
        if (r <= a || b <= l) { return; }
        if (a <= l && r <= b) { 
            lazy[k] = op3(lazy[k], o);
            return;
        }
        push(k, l, r);
        const int mid = (l + r) / 2;
        update_child(a, b, k*2 + 1, l, mid, o);
        update_child(a, b, k*2 + 2, mid, r, o);
        data[k] = op1(op2(data[k*2 + 1], lazy[k*2 + 1], l, mid), op2(data[k*2 + 2], lazy[k*2 + 2], mid, r));
    } 

    // データ配列の区間[a,b]に、oで表される演算を行う。update_childと異なり閉区間
    void update(const int a, const int b, int128_t o) {
        update_child(a, b+1, 0, 0, n, o);
    }

    // データ配列の要素1つに、oで表される演算を行う。
    void update_spot(const int a, int128_t o) {
        update_child(a, a+1, 0, 0, n, o);
    }
};

class BIT {
    // Binary Indexed Tree : 数列要素1つへの加算、数列のある地点までの累積和を高速に計算
    public:
    std::vector<long long> data;
    BIT() {}
    BIT(const int size) {
        // 想定されるサイズの2倍の値を入れた方がいいかもしれない。数列は1から数えることを想定している。
        data.resize(size, 0);
    }
    void reset() {
        for (int i = 0; i < data.size(); i++) {
            data[i] = 0;
        }
    }
    long long sum(int i) const {
        long long s = 0;
        while (i > 0) {
            s += data[i];
            i = i & (i-1); // iの最後のビットを引く。
        }
        return s;
    }

    long long sum_mod(int i, long long mod) const {
        long long s = 0;
        while (i > 0) {
            s = (s + data[i] + mod) % mod;
            i = i & (i-1); // iの最後のビットを引く。
        }
        return s;
    }

    long long val(int i) const {
        if (i == 1) { return sum(i); }
        else {
            return sum(i) - sum(i-1);
        }
    }

    long long val_mod(int i, long long mod) const {
        if (i == 1) { return sum(i); }
        else {
            return (sum(i) - sum(i-1) + mod) % mod;
        }
    }

    void add(int i, long long x) {
        while (i < data.size()) {
            data[i] += x;
            i += i - (i & (i-1)); // iの最後のビットを加算する。
        }
    }

    void add_mod(int i, long long x, long long mod) {
        while (i < data.size()) {
            data[i] = (data[i] + x + mod) % mod;
            i += i - (i & (i-1)); // iの最後のビットを加算する。
        }
    }
};

const int MAX_N = 100010;
int64_t N;
int64_t a[MAX_N];

int flag[MAX_N], ac[MAX_N];
//RQ<ADD_SUM> rq = RQ<ADD_SUM>(MAX_N);
BIT bit = BIT(MAX_N);

int64_t calc(int64_t v) {
    ac[0] = 0;
    for (int i = 1; i <= N; i++) {
        flag[i] = (v <= a[i]) ? 1 : -1;
        ac[i] = ac[i-1] + flag[i];
    }
    auto ac_compress = coordinate_compress<int>(ac, 0, N);
    //rq.reset();
    //rq.update_spot(ac_compress[ac[0]], 1);
    bit.reset();
    bit.add(ac_compress[ac[0]], 1);

    int64_t ret = 0;
    for (int i = 1; i <= N; i++) {
        //ret += rq.query(1, ac_compress[ac[i]]);
        //rq.update_spot(ac_compress[ac[i]], 1);
        ret += bit.sum(ac_compress[ac[i]]);
        bit.add(ac_compress[ac[i]], 1);
    }
    return ret;
}
 
int main(int argc, char **argv) {
    std::cin >> N;

    for (int i = 1; i <= N; i++) {
        std::cin >> a[i];
    }

    auto compress = coordinate_compress<int64_t>(a, 1, N);
    auto expand = coordinate_expand(compress);
    BSR bsr = binary_search(1, compress.size(), [&](const int i) {
        return calc(expand[i]) * 2 >= N * (N + 1) / 2;
    });
    assert(bsr.found);
    std::cout << expand[bsr.end] << std::endl;

    return 0;
}

Measured memory_bytes: 12380