#include <bits/stdc++.h>

using namespace std;

#define REP(i, N) for (int (i) = 0; (i) < (N); ++(i))
#define READALL(c) for (auto &e : c) { cin >> e; }
#define PRINTALL(c) for (const auto &e : c) { cout << e << " "; } cout << "\n";

template <typename T>
using V = vector<T>;

typedef long double ld;
typedef long long ll;

typedef int data_t;

bool in(data_t p, data_t l, data_t r) {
	return p >= l && p <= r;
}

bool in(data_t ql, data_t qr, data_t l, data_t r) {
	return in(ql, l, r) && in(qr, l, r);
}

data_t base_value = 0;
data_t identity = 0;
struct SegTree {
	// Base value is the "initial" value of any index.
	// The identity value for f (0 for +, 1 for *, INF for min, etc).
	data_t l, r, val;
	unique_ptr<SegTree> children[2];
	SegTree(data_t l, data_t r) : l(l), r(r) {}
	data_t f(data_t a, data_t b) {
		return a+b;
	}
	void recompute() {
		data_t left = base_value, right = base_value;
		if (children[0] != nullptr)
			left = children[0]->val;
		if (children[1] != nullptr)
			right = children[1]->val;
		val = f(left, right);
	}
	data_t query(data_t ql, data_t qr) {
		if (l == ql && r == qr)
			return val;
		data_t left = identity, right = identity;
		data_t mid = l + (r-l+1)/2;
		if (l == r-1)
			mid = l;
		if (ql <= mid) {
			if (children[0] == nullptr)
				left = base_value;
			else 
				left = children[0]->query(ql, qr < children[0]->r ? qr : children[0]->r);
		}
		if (qr > mid) {
			if (children[1] == nullptr)
				right = base_value;
			else
				right = children[1]->query(ql < children[1]->l ? children[1]->l : ql, qr);
		}
		return f(left, right);
	}
	data_t update(data_t index, data_t v) {
		if (l == r) {
			return val = v;
		}
		data_t mid = l + (r-l+1)/2;
		if (l == r-1)
			mid = l;
		if (in(index, l, mid)) {
			if (children[0] == nullptr)
				children[0] = unique_ptr<SegTree>(new SegTree(l, mid));
			children[0]->update(index, v);
		} else if (in(index, mid+1, r)) {
			if (children[1] == nullptr)
				children[1] = unique_ptr<SegTree>(new SegTree(mid+1, r));
			children[1]->update(index, v);
		}
		recompute();
		return val;
	}
};


int solve(V<int> A) {
	int N = A.size();
	auto sorted = A;
	sort(sorted.begin(), sorted.end());
	sorted.push_back(1e9+5);
	int lo = 0, hi = A.size();
	while (lo <= hi) {
		int mid = (lo+hi)/2;
		int v = sorted[mid];
		ll cnt = 0;
		SegTree st(-N-1, N+1);
		st.update(0, 1);
		int sum = 0;
		map<int, int> cnts;
		cnts[0] = 1;
		for (int i = 0; i < A.size(); ++i) {
			if (A[i] <= v) ++sum;
			else --sum;
			if (sum == 0) cnt += st.query(-N-1, -1);
			else if (sum > 0) cnt += st.query(-N-1, sum-1);
			else cnt += st.query(-N-1, sum-1);
			// cout << i << " " << sum << " " << cnt << endl;
			st.update(sum, cnts[sum]+1);
			cnts[sum]++;
		}
		// cout << " " << mid << " " << v << " " << cnt << endl;
		ll med = (ll)N*(N+1ll)/2ll/2ll+1;
		if (cnt < med) {
			lo = mid+1;
		} else if (cnt == med) {
			lo = mid;
			break;
		} else {
			hi = mid-1;
		}
	}

	return sorted[lo];
}

int brute(V<int> A) {
	int N = A.size();
	V<int> meds;
	for (int i = 0; i < N; ++i) {
		V<int> arr;
		for (int j = i; j < N; ++j) {
			arr.push_back(A[j]);
			sort(arr.begin(), arr.end());
			// PRINTALL(arr);
			// cout << (arr.size() == 1 ? arr[0] : arr[arr.size()/2]) << endl;
			meds.push_back(arr.size() == 1 ? arr[0] : arr[arr.size()/2]);
		}
		// cout << "   " << arr.size() << " " << arr[arr.size()/2+1] << endl;
	}
	sort(meds.begin(), meds.end());
	PRINTALL(meds);
	return meds[meds.size()/2];
}

void test() {
	default_random_engine re;
	int N = 7;
	REP(i, 10000) {
		V<int> A(N);
		REP(i, N) A[i] = re()%5+1;
		PRINTALL(A);
		cout << solve(A) << " " << brute(A) << endl;
		assert(solve(A) == brute(A));
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	// test();
	// return 0;

	int N;
	cin >> N;
	V<int> A(N);
	READALL(A);

	cout << solve(A) << endl;
	// cout << brute(A) << endl;

	
}

Measured memory_bytes: 15480