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

// clang-format off
#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); ++(i))
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); --(i))

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define endl '\n'
#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

constexpr i32 mod   = 1e9 + 7;
constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

constexpr int dx[] = {0, -1, 1, 0, -1, 1, -1, 1}; 
constexpr int dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};

struct IoSetup { IoSetup(int x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } 
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }

template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// clang-format on

template <typename T> struct BIT {
  int n;
  vector<T> bit;
  // 1-indexed
  BIT(int n_) : n(n_ + 1), bit(n + 1, 0) {}

  T sum(int i) {
    T s(0);
    for (int x = i; x > 0; x -= (x & -x))
      s += bit[x];
    return s;
  }

  void add(int i, T a) {
    if (i == 0)
      return;
    for (int x = i; x <= n; x += (x & -x))
      bit[x] += a;
  }

  // [l, r)
  T query(int l, int r) { return sum(r - 1) - sum(l - 1); }

  int lower_bound(int w) {
    if (w <= 0)
      return 0;
    int x = 0, r = 1;
    while (r < n)
      r <<= 1;
    for (int k = r; k > 0; k >>= 1) {
      if (x + k <= n && bit[x + k] < w) {
        w -= bit[x + k];
        x += k;
      }
    }
    return x + 1;
  }

  // 0-indexed
  T sum0(int i) { return sum(i + 1); }
  void add0(int i, T a) { add(i + 1, a); }
  T query0(int l, int r) { return sum(r) - sum(l); }
};

void solver() {
  i64 N = input();
  vector<i32> v(N);
  cin >> v;

  auto c = v;
  whole(sort, c);
  c.erase(whole(unique, c), c.end());

  auto check = [&](i64 x) {
      BIT<i64> bit(3 * N);
      i64 r = N + 1;
      i64 cnt = 0;

      bit.add(r, 1);
      range(i, 0, N) {
          r += (v[i] >= x ? 1 : -1);
          cnt += bit.sum(r);
          bit.add(r, 1);
      }

      return cnt >= (N * (N + 1)) / 2 / 2;
  };

  i32 ok = 0, ng = c.size();
  while (ng - ok > 1) {
    i32 mid = (ok + ng) / 2;

    if (check(c[mid])) {
      ok = mid;
    } else {
      ng = mid;
    }
  }

  cout << c[ok] << endl;
}

signed main(int argc, char *argv[]) { solver(); }


Measured memory_bytes: 3424