#include <bits/stdc++.h>

using namespace std;
#define int int64_t
#define fi first
#define se second
#define endl '\n'

template <typename T1, typename T2>
istream & operator >> (istream & in, pair <T1, T2> & p) {
     in >> p.fi >> p.se;
     return in;
}

template <typename T1, typename T2>
ostream & operator << (ostream & out, pair <T1, T2> p) {
     //    out << p.fi << " " << p.se;а
     out << "{" << p.fi << ", " << p.se << "}";
     return out;
}

template <typename T>
istream & operator >> (istream & in, vector <T> & arr) {
     for (auto & i : arr)
     {
          in >> i;
     }
     return in;
}

template <typename T>
ostream & operator << (ostream & out, vector <T> arr) {
     for (int i = 0; i < (int)arr.size() - 1; ++i)
          out << arr[i] << " ";
     if (arr.size())
          out << arr.back();
     out << endl;
     return out;
}

template <typename T>
ostream & operator << (ostream & out, set <T> & s) {
     for (auto x : s)
          out << x << " ";
     out << endl;
     return out;
}

const int mod = 1000000007;
int toadd = 1e5;
int mxind = 4e5 - 1;
int t[(int)9e5];

void build(vector<int>&a,int v, int l, int r) {
     if (l == r) {
          t[v] = a[l];
     } else {
          int m = (l + r) / 2;
          build(a, v * 2, l, m);
          build(a, v * 2 + 1, m + 1, r);
     }
}

void update(int v, int tl, int tr, int pos, int val) {
     if (tl == tr && tr == pos) {
          t[v] += val;
          return;
     }
     if (tl == tr) {
          return;
     }
     if (tl > pos || tr < pos) {
          return;
     }
     int tm = (tl + tr) / 2;
     if (pos <= tm) {
          update(v*2, tl, tm, pos, val);
     } else {
          update(v*2 + 1, tm + 1, tr, pos, val);
     }
     t[v] = t[v*2] + t[v*2+1];
}

int ask(int v, int tl, int tr, int ql, int qr) {
     if (tr < ql || tl > qr) {
          return 0;
     }
     if (ql <= tl && tr <= qr) {
          return t[v];
     }
     int tm = (tl + tr) / 2;
     return ask(v*2, tl, tm, ql, qr) + ask(v*2+1, tm+1, tr, ql, qr);
}




signed main()
{
     srand(time(nullptr));
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     
     int n;
     cin >> n;
     vector<int> a(n);
     
     int mx = 0;
     for (int i = 0; i < n; ++i) {
          cin >> a[i];
          mx = max(mx, a[i]);
     }
     vector<int> aa = a;
     sort(aa.begin(), aa.end());
     aa.erase(unique(aa.begin(), aa.end()), aa.end());
     //n++;
     aa.push_back(2e9);
     int l =0, r = aa.size();
     vector<int> newa(n + 1);
     while (r - l > 1) {
          memset(t, 0, sizeof(t));
          int m = (r + l) / 2;
          vector<int> prefs(n + 1);

          prefs[0] = n;
          for (int i = 0; i < n; i++) {
               prefs[i + 1] = prefs[i] + (a[i] >= aa[m] ? 1 : -1);
          }
          int currans = 0;
          for (int i = 0; i < n + 1; ++i) {
               currans += ask(1, 0, 2*(n + 1), 0, prefs[i]);
               update(1, 0, 2*(n + 1), prefs[i], 1);
          }
          
          if (currans * 4 >= n * (n + 1)) {
               l = m;
          } else {
               r = m;
          }
     }
     
     cout << aa[l];
     
     return 0;
}


Measured memory_bytes: 10480