#pragma region
// Author: Wenxing Mei
//   Date: 2018-08-25 21:02
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define repv(ele, vec) for (auto &ele : vec)
#define zero(mem) memset(mem, 0, sizeof(mem))
#define sd(_) scanf("%d", &_)
#define sdd(_, __) scanf("%d%d", &_, &__)
#define sddd(_, __, ___) scanf("%d%d%d", &_, &__, &___)
#define sdddd(_, __, ___, ____) scanf("%d%d%d%d", &_, &__, &___, &____)
#define sf(_) scanf("%lf", &_)
#define sff(_, __) scanf("%lf%lf", &_, &__)
#define sfff(_, __, ___) scanf("%lf%lf%lf", &_, &__, &___)
#define sffff(_, __, ___, ____) scanf("%lf%lf%lf%lf", &_, &__, &___, &____)
#define sl(_) scanf("%lld", &_)
#define sll(_, __) scanf("%lld%lld", &_, &__)
#define slll(_, __, ___) scanf("%lld%lld%lld", &_, &__, &___)
#define sllll(_, __, ___, ____) scanf("%lld%lld%lld%lld", &_, &__, &___, &____)
#define sc(_) scanf("%c", &_)
#define ss(_) scanf("%s", _)
#define sz(x) (int)(x).size()
#define mid(a, b) (((a) + (b)) >> 1)
#define lfg(x) x << 1
#define rht(x) x << 1 | 1
#define inf 0x3f3f3f3f
#define all(container) container.begin(), container.end()
//#define MOD 19260817
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
#define get0 get<0>
#define get1 get<1>
#define get2 get<2>
#define get3 get<3>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#pragma endregion

// Read the question correctly
// What are the exact constraints?
// Look out for SPECIAL CASES (n=1? n=1000000000?) and overflow (ull vs int?)

int a[100001], b[100001];
ll n;

vi count_inversion(vi arr, ll &cnt) {
  if (arr.size() == 1) {
    cnt = 0;
    return arr;
  }

  ll a, b;

  vi left = count_inversion(vi(arr.begin(), arr.begin() + arr.size() / 2), a);
  vi right = count_inversion(vi(arr.begin() + arr.size() / 2, arr.end()), b);

  vi merged;
  size_t i = 0, j = 0;
  cnt = a + b;
  while (i < left.size() || j < right.size()) {
    if (i == left.size()) {
      merged.pb(right[j++]);
    } else if (j == right.size()) {
      merged.pb(left[i++]);
    } else {
      if (left[i] <= right[j]) {
        merged.pb(left[i++]);
      } else {
        merged.pb(right[j++]);
        cnt += left.size() - i;
      }
    }
  }
  return merged;
}

ll count(int x) {
  vi prefix(n + 1);
  prefix[0] = 0;
  rep(i, 1, n + 1) {
    prefix[i] = x <= a[i - 1] ? 1 : -1;
    prefix[i] += prefix[i - 1];
  }

  ll ans;
  count_inversion(prefix, ans);
  return n * (n + 1) / 2 - ans;
}

int main() {
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  sl(n);

  ll halfCnt = n * (n + 1) / 4;

  int maxa = 1;
  rep(i, 0, n) {
    sd(a[i]);
    maxa = max(maxa, a[i]);
    b[i] = a[i];
  }

  sort(b, b + n);
  // int l = 0, r = n - 1;
  int l = 1, r = maxa;
  int res = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    ll cnt = count(mid);

    if (cnt >= halfCnt) {
      res = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }

  int idx = lower_bound(b, b + n, res) - b;
  if (b[idx] != res) { res = b[idx] - 1; }
  printf("%d\n", res);

  return 0;
}


Measured memory_bytes: 3532