#include <cstdio>
#include <cstring>
#include <cctype>
#include <cassert>
#include <iostream>
using std::cin; using std::cout; using std::endl;
#include <algorithm>
using std::sort;
#include <vector>
using std::vector;
#include <map>
using std::map;
#include <set>
using std::set;
#include <queue>
using std::queue; using std::priority_queue;
#include <utility>
using std::pair;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
#define pass printf("%s : Line.%d\n", __FUNCTION__, __LINE__);

bool chmin(int &a, const int &b) { return a > b ? a = b, true : false; }
bool chmax(int &a, const int &b) { return a < b ? a = b, true : false; }
bool chmin(LL &a, const LL &b) { return a > b ? a = b, true : false; }
bool chmax(LL &a, const LL &b) { return a < b ? a = b, true : false; }
int readint() {
	int a = 0, po = 1; char c = getchar();
	while(isspace(c)) c = getchar();
	if(c == '-') po = -1, c = getchar();
	while(isdigit(c)) a = a*10 + c - '0', c = getchar();
	return a * po;
}
LL readLL() {
	LL a = 0, po = 1; char c = getchar();
	while(isspace(c)) c = getchar();
	if(c == '-') po = -1, c = getchar();
	while(isdigit(c)) a = a*10 + c - '0', c = getchar();
	return a * po;
}

const int maxN = 100000 + 233;
const int maxA = 1000000000 + 233;
int n, a[maxN];
int x[maxN];

struct FenwickTree {
	int n, C[maxN];
	void init(int n) {
		this->n = n + 2;
		for(int i = 0; i <= n + 2; ++i) C[i] = 0;
	}
	void add(int p, int x) {
//		printf("add : p = %d\n", p);
		p += n / 2;
		for(int i = p; i <= n; i += i & -i) C[i] += x;
	}
	int sum(int p) {
//		printf("sum : p = %d\n", p);
		p += n / 2;
		int ret = 0;
		for(int i = p; i > 0; i -= i & -i) ret += C[i];
		return ret;
	}
}odd, even;

int pref[maxN];
LL calc() {
	odd.init(n); even.init(n);
	int s = 0;
	pref[0] = 0;
	LL cnt = 0;
	even.add(0, 1);
	for(int i = 1; i <= n; ++i) {
		s += x[i];
		pref[i] = s;
		int dcnt = 0;
		if(i & 1) dcnt += even.sum((s - 1 - (i - 1) / 2))
		               + odd.sum((s - 1 - (i - 2) / 2));
		else dcnt += odd.sum((s - 1 - (i - 1) / 2))
		          + even.sum((s - 1 - (i - 2) / 2));
//		printf("%d : dcnt = %d\n", i, dcnt);
//		dcnt = 0;
//		for(int j = 0; j < i; ++j) if(s - pref[j] >= (i - j + 1) / 2) ++dcnt;
//		printf("\t\t should be %d\n", dcnt);
		cnt += dcnt;
		if(i & 1) odd.add(s - i / 2, 1);
		else even.add(s - i / 2, 1);
	}
	return cnt;
}

bool check(int M) {
	for(int i = 1; i <= n; ++i) x[i] = (a[i] >= M ? 1 : 0);
	LL t = calc();
//	cout << "M = " << M << endl << "t = " << t << endl;
//	system("pause");
	return t >= (((LL)n * (LL)(n + 1)) / 2 + 1) / 2;
}

int bf() {
	vector<int> tot; tot.clear();
	for(int i = 1; i <= n; ++i) {
		for(int j = i; j <= n; ++j) {
			vector<int> v; v.clear();
			for(int k = i; k <= j; ++k) v.push_back(a[k]);
			std::sort(v.begin(), v.end());
			tot.push_back(v[(v.size()) / 2]);
		}
	}
	std::sort(tot.begin(), tot.end());
	return tot[(tot.size()) / 2];
}

int main() {
	n = readint();
	for(int i = 1; i <= n; ++i) a[i] = readint();
	int L = 1, R = 0;
	for(int i = 1; i <= n; ++i) chmax(R, a[i]);
	while(L < R) {
		int M = (L + R + 1) >> 1;
		if(check(M)) L = M;
		else R = M - 1;
	}
	cout << L << endl;
//	cout << "bf : " << bf() << endl;
	return 0;
}

Measured memory_bytes: 2176