/**
 * @brief ユーザ定義リテラル
 * @author えびちゃん
 */

#ifndef H_int_literals
#define H_int_literals
#include <cstddef>
#include <cstdint>

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }

#endif  /* !defined(H_int_literals) */

/**
 * @brief 単一更新セグメント木
 * @author えびちゃん
 */

#ifndef H_basic_segment_tree
#define H_basic_segment_tree

#include <cstddef>
#include <vector>

template <typename Monoid>
class basic_segment_tree {
public:
  using value_type = Monoid;
  using size_type = size_t;

private:
  std::vector<value_type> M_c;
  size_type M_n;

public:
  basic_segment_tree() = default;
  basic_segment_tree(basic_segment_tree const&) = default;
  basic_segment_tree(basic_segment_tree&&) = default;

  explicit basic_segment_tree(size_type n): M_c(n+n), M_n(n) {}
  explicit basic_segment_tree(size_type n, value_type const& x):
    M_c(n+n, x), M_n(n)
  {
    for (size_type i = n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
  }

  template <typename InputIt>
  basic_segment_tree(InputIt first, InputIt last) {
    std::vector<value_type> tmp(first, last);
    M_n = tmp.size();
    M_c.resize(M_n);
    M_c.insert(M_c.end(), tmp.begin(), tmp.end());
    for (size_type i = M_n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
  }

  void assign(size_type n, value_type const& x) {
    M_c.assign(n+n, x);
    M_n = n;
    for (size_type i = n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
  }

  template <typename InputIt>
  void assign(InputIt first, InputIt last) {
    std::vector<value_type> tmp(first, last);
    M_n = tmp.size();
    M_c.resize(M_n);
    M_c.insert(M_c.end(), tmp.begin(), tmp.end());
    for (size_type i = M_n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
  }

  void modify(size_type i, value_type const& x) {
    i += M_n;
    M_c[i] = x;
    while (i > 1) {
      i >>= 1;
      M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
    }
  }

  void modify(size_type i, value_type&& x) {
    i += M_n;
    M_c[i] = std::move(x);
    while (i > 1) {
      i >>= 1;
      M_c[i] = M_c[i<<1|0] + M_c[i<<1|1];
    }
  }

  value_type const& operator [](size_type i) const { return M_c[i + M_n]; }

  value_type fold(size_type l, size_type r) const {
    value_type resl{}, resr{};
    l += M_n;
    r += M_n;
    while (l < r) {
      if (l & 1) resl += M_c[l++];
      if (r & 1) resr = M_c[--r] + std::move(resr);
      l >>= 1;
      r >>= 1;
    }
    return resl += resr;
  }
};

#endif  /* !defined(H_basic_segment_tree) */

#include <cstdio>
#include <algorithm>
#include <tuple>
#include <utility>
#include <vector>

bool f(std::vector<int> const& a, int x) {
  size_t n = a.size();
  std::vector<std::pair<int, size_t>> b(n);
  for (size_t i = 0; i < n; ++i)
    b[i] = std::make_pair((a[i] < x)? -1: +1, i+1);

  b.insert(b.begin(), std::make_pair(0, 0_zu));
  for (size_t i = 1; i <= n; ++i) b[i].first += b[i-1].first;
  std::sort(b.rbegin(), b.rend());

  uintmax_t res = 0;
  basic_segment_tree<int> st(n+1, 0);
  for (auto const& p: b) {
    int bi;
    size_t i;
    std::tie(bi, i) = p;
    res += st.fold(i+1, n+1);
    st.modify(i, st[i]+1);
  }

  uintmax_t m = n * (n+1_ju) / 2;
  return m/2 <= res;
}

int main() {
  size_t n;
  scanf("%zu", &n);

  std::vector<int> a(n);
  for (auto& ai: a) scanf("%d", &ai);

  auto b = a;
  std::sort(b.begin(), b.end());

  size_t lb = 0;
  size_t ub = n;
  while (ub-lb > 1) {
    size_t mid = (lb+ub) >> 1;
    (f(a, b[mid])? lb: ub) = mid;
  }
  printf("%d\n", b[lb]);
}


Measured memory_bytes: 5832