#include <iostream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <limits>
#include <algorithm>
#include <array>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <unordered_map>
#include <random>
#include <cmath>
#include <complex>

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

const int INFL = (int)1e9;
const ll INFLL = (ll)1e18;
const double INFD = numeric_limits<double>::infinity();
const double PI = 3.14159265358979323846;
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loopll(i, n) for(ll i = 0; i < (ll)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopll1(i, n) for(ll i = 1; i <= (ll)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Looprll(i, n) for(ll i = (ll)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define Looprll1(i, n) for(ll i = (ll)n; i >= 1; i--)
#define Loopitr(itr, container) for(auto itr = container.begin(); itr != container.end(); itr++)
#define printv(vector) Loop(i, vector.size()) { cout << vector[i] << " "; } cout << endl;
#define printmx(matrix) Loop(i, matrix.size()) { Loop(j, matrix[i].size()) { cout << matrix[i][j] << " "; } cout << endl; }
#define rndf(d) (ll)((double)(d) + (d >= 0 ? 0.5 : -0.5))
#define floorsqrt(x) ((ll)sqrt((double)x) + ((ll)sqrt((double)x) * (ll)sqrt((double)x) <= (ll)(x) ? 0 : -1))
#define ceilsqrt(x) ((ll)sqrt((double)x) + ((ll)x <= (ll)sqrt((double)x) * (ll)sqrt((double)x) ? 0 : 1))
#define rnddiv(a, b) ((ll)(a) / (ll)(b) + ((ll)(a) % (ll)(b) * 2 >= (ll)(b) ? 1 : 0))
#define ceildiv(a, b) ((ll)(a) / (ll)(b) + ((ll)(a) % (ll)(b) == 0 ? 0 : 1))
#define quickio() ios::sync_with_stdio(false); cin.tie(0);
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)

/*******************************************************/

class Binary_Indexed_Tree {
private:
	vll bits;
	int n;
public:
	Binary_Indexed_Tree(vll a) {
		n = a.size();
		bits = vll(n, 0);
		Loop(i, a.size()) add(i, a[i]);
	}
	void add(int k, ll x) {
		++k;
		for (int index = k; index <= n; index += index & -index) {
			bits[index - 1] += x;
		}
	}
	// note: sum of [s, t)
	ll sum(int s, int t) {
		ll ret = 0;
		for (int index = t; index > 0; index -= index & -index) {
			ret += bits[index - 1];
		}
		for (int index = s; index > 0; index -= index & -index) {
			ret -= bits[index - 1];
		}
		return ret;
	}
};

// solve the number of pair(i, j) such that a[i] > a[j] (i < j) 
ll solve_inversion_number(const vll &a) {
	int n = a.size();
	map<ll, int> mp;
	Loop(i, n) mp[a[i]] = 1;
	int cnt = 0;
	Loopitr(itr, mp) itr->second = cnt++;
	vi b(n);
	Loop(i, n) b[i] = mp[a[i]];
	Binary_Indexed_Tree bit(vll(cnt, 0));
	ll ret = 0;
	Loop(i, n) {
		ret += bit.sum(b[i] + 1, cnt);
		bit.add(b[i], 1);
	}
	return ret;
}

template<typename argv_t>
class Binary_Search {
private:
	argv_t argv;
	bool(*evalfunc)(ll, argv_t);
	ll search(ll l, ll r) {
		if (r - l == 1) return l;
		ll m = (l + r) / 2;
		if (evalfunc(m, argv)) return search(m, r);
		else return search(l, m);
	}
public:
	ll result;
	// range = [l, r), return last value causing "t" in evalfunc that returns l->[t,...,t,f,...,f)->r
	Binary_Search(pair<ll, ll> range, argv_t argv, bool(*evalfunc)(ll, argv_t)) {
		Binary_Search::argv = argv;
		Binary_Search::evalfunc = evalfunc;
		result = search(range.first, range.second);
	}
};

vll b;

bool evalfunc(ll val, vll a) {
	ll n = a.size();
	ll cnt = 0;
	Loop(i, n) {
		if (a[i] >= b[(int)val]) a[i] = 1;
		else a[i] = -1;
	}
	vll s((int)n + 1);
	s[0] = 0;
	Loop1(i, n) {
		s[i] = s[i - 1] + a[i - 1];
	}
	cnt += n * (n + 1) / 2 - solve_inversion_number(s);
	if (cnt >= ceildiv(n * (n + 1) / 2, 2)) return true;
	else return false;
}

int main() {
	int n; cin >> n;
	vll a = vll(n); Loop(i, n) cin >> a[i];
	b = a;
	sort(b.begin(), b.end());
	Binary_Search<vll> bs({0, n}, a, evalfunc);
	cout << b[(int)bs.result] << endl;
}

Measured memory_bytes: 13200