// Original C++ solution (slower):
#include<bits/stdc++.h>

#include<ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

using namespace std;

typedef long long ll;

typedef long double ld;

#define pb push_back

#define X first

#define Y second

#define sz(v) (int)v.size()

using ord = tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update>;



void solve();



main() {

	ios_base::sync_with_stdio(0), cin.tie(0);

#ifdef ONPC

	freopen("in.txt", "r", stdin);

#endif

	int t = 1;

	//cin >> t;

	while (t--) solve();

	return 0;

}



const int N = 1e5 + 5;

int n, a[N], fenv[N + N];



void inic() {

	for (int i= 0; i < N + N; ++i) fenv[i] = 0;

}



void inc(int r, int add) {

	for (; r < N + N; r += r & -r) fenv[r] +=add;

}



int get(int r) {

	int res= 0;

	for (; r > 0; r -= r & -r) res += fenv[r];

	return res;

}



void solve() {

	cin >> n;

	for (int i = 1; i <= n; ++i) cin >> a[i];

	if (n == 1) {

		cout << a[1] << '\n';

		return;

	}

	ll all = (ll)n * (ll)(n) / (ll)2;

	int lef = 0, rig = 1e9 + 1;

	while (rig - lef > 1) {

		int mid = (lef + rig) / 2;

		ll cur = 0;

		inic();

		inc(N, 1);

		int bal = 0;

		for (int i = 1; i <= n; ++i) {

			int x = a[i];

			if (x >= mid) x = 1;

			else x = -1;

			bal += x;

			cur += get(N + bal);

			inc(N + bal, 1);

		}

		if (cur * 2 >= all) {

			lef = mid;

		} else {

			rig = mid;

		}

	}

	cout << lef << '\n';

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;

#define int long long

#define x first

#define y second



#define vert int v, int tl, int tr

#define tm ((tl + tr) >> 1)

#define left (v << 1), tl, tm

#define right (v << 1) + 1, tm, tr



typedef pair<int, int> pii;

typedef long long ll;

typedef long double ld;



int n;

int a[100009];

int pref[100009];



int tree[800009];

void build(vert) {

    tree[v] = 0;

    if (tr - tl == 1) return;



    build(left);

    build(right);

}



void upd(vert, int i, int x) {

    tree[v] += x;

    if (tr - tl == 1) {

        return;

    }



    if (i < tm) {

        upd(left, i, x);

    }



    else {

        upd(right, i, x);

    }

}



int getsum(vert, int l, int r) {

    if (l >= tr || tl >= r) return 0;

    if (tl >= l && tr <= r) return tree[v];

    return getsum(left, l, r) + getsum(right, l, r);

}



int check(int x) {

    for (int i = 0; i < n; i ++) {

        if (a[i] >= x)

            pref[i + 1] = pref[i] + 1;

        else

            pref[i + 1] = pref[i] - 1;

    }



    build(1, 0, 2 * n + 2);

    int cnt = 0;

    for (int i = 0; i <= n; i ++) {

        cnt += getsum(1, 0, 2 * n + 2, 0, pref[i] + n + 1);

        upd(1, 0, 2 * n + 2, pref[i] + n, 1);

    }



    return cnt;

}



signed main() {

    ios :: sync_with_stdio(0);

    cin.tie(0);



    cin >> n;

    for (int i = 0; i < n; i ++) {

        cin >> a[i];

    }



    int l = 0, r = (1e9) + 1;

    int eth = (n * n) / 2;

    while (r - l > 1) {

        int m = (r + l) / 2;

        if (check(m) <= (eth + 1) / 2) {

            r = m;

        }



        else {

            l = m;

        }

    }



    cout << l;



    return 0;

}


// Fastest known solution for this problem: