//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>

#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

#include <stdexcept>

using namespace std;

//conversion
//------------------------------------------
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class t> inline string tostring(t x) { ostringstream sout; sout << x; return sout.str(); }

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (l" << __line__ << ")" << " " << __file__ << endl

// type alias
using ll = long long;
using ull = unsigned long long;

inline bool isPower2(ull a)
{
	if (a == 0)
	{
		return false;
	}
	return !(a & (a - 1));
}

inline ll getMaxEffectiveBit(ull a)
{
	ll index = -1;
	for (; a != 0; a >>= 1)
	{
		++index;
	}
	return index;
}

inline ll getSpecifiedBit(ull a, unsigned bit)
{
	return (a & (1LL << bit)) >> bit;
}

// computational complexity: o(log(max(a, b))) 
inline ull getGcd(ull a, ull b)
{
	if (b == 0)
	{
		return a;
	}
	return getGcd(b, a % b);
}

template<class Integer>
inline Integer getPower(Integer base, unsigned exponential)
{
	Integer res = 1;
	while (exponential >= 1)
	{
		if (exponential & 1)
		{
			res *= base;
		}
		base = base * base;
		exponential >>= 1;
	}

	return res;
}

template<class Integer>
class BinaryIndexedTree
{
private:
	ull maxSize_;
	vector<Integer> values_;
public:
	BinaryIndexedTree(ull maxSize) : maxSize_(maxSize), values_(maxSize_, 0) {}

	void update(ll index, Integer increment)
	{
		if (maxSize_ <= index)
		{
			throw invalid_argument("Index should be less than maxSize.");
		}
		++index;

		while (index <= maxSize_)
		{
			values_[index - 1] += increment;
			index += index & -index;
		}
	}

	Integer query(ll index)
	{
		if (maxSize_ <= index)
		{
			throw invalid_argument("Index should be less than maxSize.");
		}
		++index;

		Integer res = 0;
		while (index > 0)
		{
			res += values_[index - 1];
			index -= index & -index;
		}
		return res;
	}
};
using bitll = BinaryIndexedTree<ll>;



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

	ll N;
	cin >> N;

	vector<ll> as(N);
	for (ll i = 0; i < N; ++i)
	{
		cin >> as[i];
	}

	double leftVal = 0;
	double rightVal = 1000000000;
	double checkVal = (leftVal + rightVal) / 2;
	vector<ll> accumCounts(N);
	
	while (rightVal - leftVal >= 0.01)
	{
		ll accumCount = 0;
		for (ll i = 0; i < N; ++i)
		{
			if (as[i] >= checkVal)
			{
				++accumCount;
			}
			else {
				--accumCount;
			}
			accumCounts[i] = accumCount;
		}

		auto minAccumCount = *min_element(accumCounts.begin(), accumCounts.end());
		auto maxAccumCount = *max_element(accumCounts.begin(), accumCounts.end());
		bitll bit(maxAccumCount - minAccumCount + 1);

		ll res = 0;
		for (ll i = 0; i < N; ++i)
		{
			if (accumCounts[i] >= 0)
			{
				++res;
			}
			res += bit.query(accumCounts[i] - minAccumCount);
			bit.update(accumCounts[i] - minAccumCount, 1);
		}

		if (res >= ( ((N + 1) * N / 2 + 1) / 2) )
		{
			leftVal = checkVal;
		}
		else
		{
			rightVal = checkVal;
		}
		checkVal = (leftVal + rightVal) / 2;
	}

	cout << ll(rightVal) << endl;

	return 0;
}


Measured memory_bytes: 2672