#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(),x.end()
#define ln '\n'
const double PI = acos(-1.0);
const long long MOD = 1000000007LL;
//const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
///////////////////////////////////////////////////////////////////////////////////////////////////

template<typename T>
struct Compress {
  vector<T> xs;

  Compress() = default;

  Compress(const vector<T> &vs) {
    add(vs);
  }

  Compress(const initializer_list<vector<T>> &vs) {
    for(auto &p : vs) add(p);
  }

  void add(const vector<T> &vs) {
    copy(begin(vs), end(vs), back_inserter(xs));
  }

  void add(const T &x) {
    xs.emplace_back(x);
  }

  void build() {
    sort(begin(xs), end(xs));
    xs.erase(unique(begin(xs), end(xs)), end(xs));
  }

  vector<int> get(const vector<T> &vs) const {
    vector<int> ret;
    transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x) {
      return lower_bound(begin(xs), end(xs), x) - begin(xs);
    });
    return ret;
  }

  int get(const T &x) const {
    return lower_bound(begin(xs), end(xs), x) - begin(xs);
  }

  const T &operator[](int k) const {
    return xs[k];
  }
};

template<typename T>
struct BinaryIndexedTree {
    int N;
    vector<T> data;

    BinaryIndexedTree(int sz) {
        N = sz;
        data.assign(++sz, 0);
    }

    T sum(int k) { // [0,k) (0-indexed) a[0] + … + a[k-1]
        T ret = 0;
        for(; k > 0; k -= k & -k) ret += data[k];
        return (ret);
    }

    T sum(int l, int r) { // [l,r) (0-indexed) a[l] + …　+ a[r-1]
        T vl = sum(l);
        T vr = sum(r);
        return vr - vl;
    }

    void add(int k, T x) { // (0-indexed) a[k] += x;
        for(++k; k <= N; k += k & -k) data[k] += x;
    }

    int lowerbound(int x) { // (0-indexed)
        int k = 1;
        int res = 0;
        while ((k<<1) <= N) k <<= 1;
        while (k > 0) {
            if (res + k <= N && data[res+k] < x) {
                x -= data[res+k];
                res += k;
            }
            k >>= 1;
        }
        return res;
    }

    int upperbound(int x) { // (0-indexed)
        ++x;
        int k = 1;
        int res = 0;
        while ((k<<1) <= N) k <<= 1;
        while (k > 0) {
            if (res + k <= N && data[res+k] < x) {
                x -= data[res+k];
                res += k;
            }
            k >>= 1;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll N; cin >> N;
    vector<int> A(N),C(N+1);
    rep(i,N) cin >> A[i];

    ll check = N*(N+1)/2;
    check = check/2+1;
    vector<pii> B(N);
    rep(i,N) B[i] = {A[i],i};
    sort(all(B));
    int ng = -1;
    int ok = N-1;
    while (ok - ng > 1) {
        int mid = (ng+ok)/2;
        int num = B[mid].second;
        int val = A[num];
        rep(i,N) {
            if (A[i] > val) C[i+1] = 1;
            else C[i+1] = -1;
            C[i+1] += C[i]; 
        }
        Compress<int> Com(C);
        Com.build();
        auto D = Com.get(C);
        BinaryIndexedTree<ll> BIT(N+1);
        ll cnt = 0;
        rep(i,N+1) {
            cnt += BIT.sum(D[i]+1,N+1);
            BIT.add(D[i],1);
        }
        if (cnt < check) ng = mid;
        else ok = mid;
    }

    cout << B[ok].first << ln;
}

Measured memory_bytes: 3976