#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <cctype>
#include <unordered_set>
#include <unordered_map>
#include <numeric>

using namespace std;

#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,b,e) for(int i = (b); i <= (e); i++)

#define pr(x) do{cerr << (#x) << " = " << (x) << endl;}while(0)
#define pri(x,i) do{cerr << (#x) << "[" << i << "] = " << (x[i]) << endl;}while(0)

namespace std {
	template<class S, class T> pair<S, T> operator + (const pair<S, T> &a, const pair<S, T> &b) {return mp<S, T>(a.first + b.first, a.second + b.second);}
	template<class S, class T> pair<S, T> operator - (const pair<S, T> &a, const pair<S, T> &b) {return mp<S, T>(a.first - b.first, a.second - b.second);}
	template<class S, class T> pair<S, T>& operator += (pair<S, T> &a, const pair<S, T> &other) {return a = a + other;}
	template<class S, class T> pair<S, T>& operator -= (pair<S, T> &a, const pair<S, T> &other) {return a = a - other;}
	template<class S, class T> ostream& operator << (ostream& ost, pair<S, T> p) {ost << "(" << p.first << ", " << p.second << ")";return ost;}
	template<class T> ostream& print_iterable_container(ostream& ost, T& container) {
		for (auto&& iter = begin(container); iter != end(container); ++iter) ost << (iter == begin(container) ? " [ " : ", ") << (*iter);
		return ost << " ]";
	}
#	define APPLY_PRINT_ITERABLE_CONTAINER(container_type)\
	template<class T> ostream& operator << (ostream& ost, container_type<T>& container) {\
		return print_iterable_container(ost, container);\
	}
	APPLY_PRINT_ITERABLE_CONTAINER(vector);
	APPLY_PRINT_ITERABLE_CONTAINER(list);
	APPLY_PRINT_ITERABLE_CONTAINER(deque);
}

template<class T> inline bool CHMAX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool CHMIN(T &l,const T &r){return l>r?l=r,1:0;}

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vpii = vector<pii>;
using vpll = vector<pll>;

using ld = long double;

#define UNIQUE(v) do{ (v).erase( unique(begin(v), end(v)), end(v) ); } while(0)
template<class T> using VV = vector<vector<T> >;
template<class T> using maxPQ = priority_queue<T>;
template<class T> using minPQ = priority_queue<T, vector<T>, greater<T> >;
template<class T, class U> using umap = unordered_map<T, U>;
template<class T> using uset = unordered_set<T>;

const ll INF = 1001001001;
const ll INFll = (ll)INF * INF;
const ll MOD = 1000000007;
const ll MOD_FFT = 998244353;
const ld EPS = 1e-15;

//function<void(int,int)> tensi_no_3p=[&](int v,int d){
//};

ll N, M;
vll A, X, B, C;

void add(int k, int x) {
	while (k < B.size()) {
		B[k] += x;
		k += k & -k;
	}
}

ll sum(int k) {
	ll ret = 0;
	while (k > 0) {
		ret += B[k];
		k -= k & -k;
	}
	return ret;
}

namespace util {
	// Example:
	//     vi idx = util::argsort(begin(v), end(v), greater<int>());
	//     int min_value = v[idx[0]];
	//     vi rank = util::inv_map(idx);
	//     int order_of_first_element = rank[0];

	template <class RandomAccessIterator, class Compare>
	vi argsort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) {
		// initialize original index locations
		vi idx(distance(first, last));
		iota(idx.begin(), idx.end(), 0);

		// sort indexes based on comparing values in v
		sort(idx.begin(), idx.end(), [&first, &comp](int i1, int i2) { return comp(first[i1], first[i2]); });

		return move(idx);
	}
	// Coordinates Compression
	struct CoordComp {
		vll i2v;  // index to value
		umap<ll, int> v2i;  // value to index
		CoordComp() {}
		template<class T> CoordComp(const vector<T> &vals) : i2v(vals.size()) {
			copy(begin(vals), end(vals), begin(i2v));
			sort(begin(i2v), end(i2v));
			UNIQUE(i2v);
			int n = i2v.size();
			rep(i, n) v2i[i2v[i]] = i;
		}
		int size() const {
			return i2v.size();
		}
	};
};

int main() {
	ios_base::sync_with_stdio(false);
	cin >> N;
	A.resize(N);
	X.resize(N);
	ll t = 1; while (t <= N + 1) t *= 2;
	B.resize(t);
	rep(i, N) cin >> A[i];
	M = N * (N + 1) / 2;
	int left = 0, right = INF;
	while (right - left > 1) {
		int middle = (left + right) / 2;
		rep(i, N) X[i] = A[i] >= middle ? 1 : -1;
		C.resize(N + 1);
		C[0] = 0;
		rep(i, N) C[i + 1] = C[i] + X[i];
		fill(begin(B), end(B), 0);
		ll ans = 0;
		util::CoordComp cc(C);
		vi fuga(N + 1);
		rep(i, N + 1) fuga[i] = cc.v2i[C[i]];
		rep(i, N + 1) {
			ans += sum(fuga[i] + 1);
			add(fuga[i] + 1, 1);
		}

		if (ans >= (M + 1) / 2) {
			left = middle;
		}
		else {
			right = middle;
		}
	}
	cout << left << endl;
	return 0;
}


Measured memory_bytes: 9024