#define DEBUG 0
#include <bits/stdc++.h>
#define loop(n) for (lint ngtkana_is_a_genius = 0; ngtkana_is_a_genius < lint(n); ngtkana_is_a_genius++)
#define rep(i, begin, end) for (lint i = lint(begin); (i) < lint(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto mt = std::mt19937_64(std::random_device{}());
auto cmn = [](auto&& a, auto b){ if (a > b) {a = b; return true;} return false; };
auto cmx = [](auto&& a, auto b){ if (a < b) {a = b; return true;} return false; };
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { std::cerr << " " << head; debug_impl(tail...); }
#if DEBUG
#define debug(...)\
  do {\
    std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_impl(__VA_ARGS__);\
    std::cerr << std::noboolalpha;\
  } while (false)
#else
#define debug(...) {}
#endif

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr>
std::istream& operator>> (std::istream& is, Container& v)
  { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr >
std::ostream& operator<< (std::ostream& os, Container const& v) {
 os << "{";
  for (auto it = v.begin(); it != v.end(); it++)
    {os << (it != v.begin() ? "," : "") << *it;}
  return os << "}";
}

template <class Seg, class SegPtr>
struct segment_tree_entry;

template <class Seg, class SegPtr, class Pointer, class Reference>
struct segment_tree_iterator;

template <typename Value, typename BinaryOp>
class segment_tree {
public:
  using value_type = Value;
  using this_type = segment_tree<Value, BinaryOp>;
  using entry_type = segment_tree_entry<this_type, this_type*>;
  using const_entry_type = segment_tree_entry<this_type, this_type const*>;
  using iterator = segment_tree_iterator<this_type, this_type*, value_type*, value_type&>;
  using const_iterator = segment_tree_iterator<this_type, this_type const*, value_type const*, value_type const&>;

friend class segment_tree_entry<this_type, this_type*>;
friend class segment_tree_entry<this_type, this_type const*>;

private:
  int                  sz, n, N;
  BinaryOp             op;
  Value                id;
  std::vector< Value > table;

  auto& op_assign(Value& x, Value y) const
    { return x = op(x, y); }
  void merge(int u)
    { table.at(u) = op(table.at(2 * u), table.at(2 * u + 1)); }

public:
  segment_tree(int sz, BinaryOp op, Value id):
    sz(sz), n(std::pow(2, int(std::log2(2*sz-1)))), N(n * 2), op(op), id(id), table (N, id) {}

  iterator begin()
    { return iterator(this, 0); }

  iterator end()
    { return iterator(this, sz); }

  const_iterator begin() const
    { return const_iterator(this, 0); }

  const_iterator end() const
    { return const_iterator(this, sz); }

  auto at(std::size_t i)
    { return entry_type(this, i); }

  auto at(std::size_t i) const
    { return table.at(n + i); }

  auto& lazy_at(std::size_t i)
    { return table.at(n + i); }

  auto& lazy_at(std::size_t i) const
    { return table.at(n + i); }

  auto collect() const {
    auto ret = std::vector<Value>(sz);
    for (auto i = 0; i < sz; i++)
      { ret.at(i) = at(i); }
    return ret;
  }

  auto query(int l, int r) const {
    auto const dfs = [&](auto&& f, int l, int r, int k, int L, int R) -> Value {
      return l <= L && R <= r ? table.at(k)
        : R <= l || r <= L ? id
        : op(f(f, l, r, 2*k, L, (L+R)/2), f(f, l, r, 2*k+1, (L+R)/2, R));
    };
    return dfs(dfs, l, r, 1, 0, n);
  }

  void build()
    { for (auto i = n - 1; i > 0; i--) merge(i); }
};

template <class Seg, class SegPtr>
class segment_tree_entry {
  using value_type = typename Seg::value_type;
  SegPtr seg;
  std::size_t i;

  auto& get() {
    return seg->table.at(seg->n+i);
  }

  void build_oneline() {
    for (int j=(i+seg->n)/2; j>0; j/=2) {
      seg->merge(j);
    }
  }

public:
  segment_tree_entry(SegPtr seg, std::size_t i) : seg(seg), i(i) {}

  operator value_type() {
    return seg->table.at(seg->n + i);
  }
  void operator=(value_type x) {
    get() = x;
    build_oneline();
  }
  void operator++() {
    get()++;
    build_oneline();
  }
  void operator--() {
    get()--;
    build_oneline();
  }
  void operator+=(value_type x) {
    get() += x;
    build_oneline();
  }
  void operator-=(value_type x) {
    get() -= x;
    build_oneline();
  }
  void operator*=(value_type x) {
    get() *= x;
    build_oneline();
  }
  void operator/=(value_type x) {
    get() /= x;
    build_oneline();
  }
};

template <class Seg, class SegPtr, class Pointer, class Reference>
class segment_tree_iterator {
  using this_type = segment_tree_iterator<Seg, SegPtr, Pointer, Reference>;
  using value_type = typename Seg::value_type;
  using pointer = Pointer;
  using reference = Reference;

  template <class Seg_, class SegPtr_, class Pointer_, class Reference_>
  friend bool operator!=(segment_tree_iterator<Seg_, SegPtr_, Pointer_, Reference_>, segment_tree_iterator<Seg_, SegPtr_, Pointer_, Reference_>);

  SegPtr seg;
  std::size_t i;

public:
  segment_tree_iterator(SegPtr seg, std::size_t i) : seg(seg), i(i) {}

  this_type& operator++(){ i++; return *this; }
  this_type  operator++(int){ auto old = *this; ++i; return old; }
  pointer operator->(){ return &seg->at(i); }
  value_type operator*(){ return seg->at(i); }
};

template <class Seg, class SegPtr, class Pointer, class Reference>
bool operator!=(segment_tree_iterator<Seg, SegPtr, Pointer, Reference> a, segment_tree_iterator<Seg, SegPtr, Pointer, Reference> b) {
  return a.i != b.i;
}

template<typename Value, typename BinaryOp>
auto make_segment_tree(int sz, BinaryOp const& op, Value id)
  { return segment_tree<Value, BinaryOp>(sz, op, id); }

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  lint n; std::cin >> n;
  lint N = n * (n + 1) / 2;
  std::vector<lint> a(n); std::cin>>a;
  debug(a);

  auto count = [&] (lint X) -> lint {
    std::vector<int> b(n+1);
    rep(i,0,n) {
      b.at(i+1) = X <= a.at(i) ? +1 : -1;
    }
    debug(X,a,b);
    std::partial_sum(all(b), b.begin());
    int geta = -*std::min_element(all(b));
    for (int& x : b) {
      x += geta;
    }
    debug(b);

    lint ans = 0;
    auto seg = make_segment_tree<int>(n+1,std::plus<>{},0);
    for (int x : b) {
      int now = seg.query(0,x+1);
      debug(x,seg,now);
      ans += now;
      ++seg.at(x);
    }
    debug(ans);
    return ans;
  };

  lint half = (N + 1) / 2;
  lint l = *std::max_element(all(a))+1, ge = 0;
  while (1 < l - ge) {
    lint X = (l + ge) / 2;
    (count(X) < half ? l : ge) = X;
  }
  lint ans = ge;
  std::cout << ans << std::endl;
  return 0;
}

/*
ex:
0 0 [1] 1 1
0 0 [1] 1

数列の中央値は、それ以上であるものが半分の切り上げ以上あるもの中で最小です。
そこで、答えを二分探索しましょう。

X を決めて、中央値が X 以上であるような区間の数を数えましょう。
区間がそうである条件は、X 以上な要素が半分の切り上げ以上であることです。
X 以上ならば +1, 以下ならば -1 と書き換えると、この条件は総和が 0 以上と書き換えられます。
累積和をとると、a[l] <= a[r] なる 0 <= l < r <= n の数を数えれば良いことがわかります。
*/

Measured memory_bytes: 2432