#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
void YN(bool flg) {cout << ((flg) ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << ((flg) ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << ((flg) ? "yes" : "no") << endl;}

//Binary Indexed Tree
class Binary_Indexed_Tree_Range_Sum_Query {
public:
	int N;
	vector<long long> node;
 
	Binary_Indexed_Tree_Range_Sum_Query(int N) : N(N), node(vector<long long>(N + 1, 0)) {
	}
 
	void update(int idx, long long var) {
		for (++idx; idx <= N; idx += idx & -idx) node[idx] += var;
	}
 
	long long getvar(int idx) {
		long long ret = 0;
		for (++idx; idx >= 1; idx -= idx & -idx) ret += node[idx];
		return ret;
	}
};
 
//Seat Pressure
class Zarts {
public:
	vector<long long> solve(const vector<long long> & ar, int cnt = 0) {
		vector<long long> ret;
		map<long long, int> mp;
		for (auto val : ar) mp[val] = 0;
		for (auto &u : mp) u.second = cnt++;
		for (auto val : ar) ret.push_back(mp[val]);
		return ret;
	}
};
 
int main() {

	ll N; cin >> N;
	V<ll> a(N+1,0); FOR(i,1,N+1) cin >> a[i];
	ll ok = *min_element(ALL(a));
	ll ng = *max_element(ALL(a))+1;
	ll th = ((N*(N+1))/2)%2?(N*(N+1))/4+1:(N*(N+1))/4;
	while(ng-ok>1){
		ll md = (ok + ng) / 2;
		auto b = a;
		FOR(i, 1, N+1) b[i] = ((b[i] >= md) ? 1 : -1);
		FOR(i, 1, N+1) b[i] += b[i - 1];
		Zarts Z;
        b=Z.solve(b);
		ll sum = 0;
		Binary_Indexed_Tree_Range_Sum_Query BIT(*max_element(ALL(b))+1);
		REP(i, N+1) {
			sum += BIT.getvar(b[i]);
			BIT.update(b[i], 1);
		}
		(sum>=th?ok:ng)=md;
	}
	print(ok);
}



Measured memory_bytes: 9924