#include <iostream>
#include <iomanip>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <vector>
#include <cassert>
#include <fstream>
#include <algorithm>
#include <list>
#include <random>
#include <ctime>
#include <cmath>
#include <random>
#include <bitset>
#include <complex>
#include <stack>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define int ll
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector< vvi > vvvi;
typedef vector<short> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<ld> vld;
typedef vector<vld> vvld;
typedef vector<vvld> vvvld;
typedef pair<ld, ld> pld;
typedef complex<double> base;

#define mmin(a, b) a = min(a, (b))
#define mmax(a, b) a = max(a, (b))
#define mp(a,b) make_pair(a,b)
#define modsum(a, b) ((a) + (b) >= M ? (a) + (b) - M : (a) + (b))
#define modsubract(a, b) ((a) - (b) < 0 ? (a) - (b) + M : (a) - (b))
#define modmultiply(a, b) (((a) * (b)) % M)
#define pb(a) push_back(a)
#define ALL(a) a.begin(),a.end()
#define sqr(x) (x) * (x)
#define fori(i, n) for(int i = 0; i < int(n); ++i)
#define cint const int &
#define SZ(a) ((int)(a.size()))
#define f(cnt) (((cnt) + 1) * (cnt) / 2)
#define watch(x) cout << (#x) << " = " << x << endl;

const double PI = 2 * acos(0.0);

template<typename T>
struct edge {
    int from, to;
    T w;
    edge(int from, int to, T w): from(from), to(to), w(w) { }
    edge() { }
};

template<class T, class C>
void show(C a) {
//    FIXME: it doesn't work
    for (T x : a)
        cout << x << " ";
    cout << endl;
}

struct node {
    int tl, tr;
    int tm;
    int val = 0;
    node *lf, *rf;
    node(int tl, int tr):tl(tl), tr(tr) {
        int div = tr - tl;
        tm = tl + (div >> 1);
        lf = NULL;
        rf = NULL;
    }

    void upd(int pos) {
        val++;
        if (tl == tr) {
            return;
        }
        if (pos <= tm) {
            if (lf == NULL) lf = new node(tl, tm);
            lf->upd(pos);
        } else {
            if (rf == NULL) rf = new node(tm + 1, tr);
            rf->upd(pos);
        }
    }
    int get(int l, int r) {
        if (l > r) return 0;
        if (l == tl && r == tr) return val;
        ll ret = 0;
        if (lf != NULL) ret += lf->get(l, min(tm, r));
        if (rf != NULL) ret += rf->get(max(tm + 1, l), r);
        return ret;
    }
    ~node() {
        if (lf != NULL) delete lf;
        if (rf != NULL) delete rf;
    }
};

const int N = 1e5 + 9;
int n;
int a[N];
int b[N];
vector<pll> kek;
ll check(int ind) {
    for (int i = 0; i < n; ++i) {
        if (i <= ind) b[kek[i].second] = 0;
        else b[kek[i].second] = 1;
    }
    int cur = 0;
    ll ans = 0;
    int l = -3* N;
    int r = 3 * N;
    node *tr = new node(-3 * N, 3 * N);
    tr->upd(0);
    for (int i = 0; i < n; ++i) {
//        watch(i);
        if (b[i] == 0) {
            cur++;
        } else {
            cur--;
        }

        ans += tr->get(l, cur - 1);
        tr->upd(cur);
    }


    delete tr;
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    ll cnt = n * (n + 1) / 2;
    ll middle = cnt / 2 + 1;
    fori (i, n) {
        cin >> a[i];
        kek.push_back(mp(a[i], i));
    }
    sort(ALL(kek));
    int l = 0, r = SZ(kek) - 1;
    while (l < r) {
        int m = (l + r) >> 1;
//        watch(m);
        if (check(m) >= middle) {
            r = m;
        } else {
            l = m + 1;
        }
    }
//    watch(l);
//    watch(r);
    cout << kek[l].first;
}

Measured memory_bytes: 12784