//#define NDEBUG
#define _CRT_SECURE_NO_WARNINGS
#include <array>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <limits>
#include <memory>
#include <string>
#include <type_traits>

class rep {
	const ::std::size_t f, l;

public:
	using value_type = ::std::size_t;
	using reference = value_type;
	class repitr {
		friend rep;
		value_type i;
		repitr(value_type x) noexcept : i(x) {}

	public:
		void operator++() noexcept { ++i; }
		reference operator*() const noexcept { return i; }
		bool operator!=(const repitr x) const noexcept { return i != x.i; }
	};
	explicit rep(value_type first, value_type last) noexcept
		: f(first), l(last) {}
	repitr begin() const noexcept { return repitr(f); }
	repitr end() const noexcept { return repitr(l); }
};
class revrep {
	const ::std::size_t f, l;

public:
	using value_type = ::std::size_t;
	using reference = value_type;
	class revrepitr {
		friend revrep;
		value_type i;
		revrepitr(value_type x) noexcept : i(x) {}

	public:
		void operator++() noexcept { --i; }
		reference operator*() const noexcept { return i; }
		bool operator!=(const revrepitr x) const noexcept { return i != x.i; }
	};
	explicit revrep(value_type first, value_type last) noexcept
		: f(first), l(last) {}
	revrepitr begin() const noexcept { return revrepitr(l - 1); }
	revrepitr end() const noexcept { return revrepitr(f - 1); }
};
template <class T> bool maxi(T &a, const T &b) {
	return b < a ? 0 : (a = b, 1);
}
template <class T> bool mini(T &a, const T &b) {
	return a < b ? 0 : (a = b, 1);
}
template <class T> bool smaxi(T &a, const T &b) {
	return a < b ? (a = b, 1) : 0;
}
template <class T> bool smini(T &a, const T &b) {
	return b < a ? (a = b, 1) : 0;
}
class customIN {
	int c;
	bool f = 0;
	void get_c() { c = fgetc(stdin); }
	bool vacant() const noexcept { return c == ' ' || c == '\n'; }
	void cueing() {
		while (get_c(), vacant())
			;
	}

public:
	template <class T>
	auto operator>>(T &d) ->
		typename ::std::enable_if<::std::is_signed<T>::value, customIN &>::type {
		d = 0;
		cueing();
		if (c == '-')
			f = 1, get_c();
		do
			d = d * 10 + c - '0';
		while (get_c(), !vacant());
		if (f)
			d = -d, f = 0;
		return *this;
	}
	template <class T>
	auto operator>>(T &d) ->
		typename ::std::enable_if<!::std::is_signed<T>::value, customIN &>::type {
		d = 0;
		cueing();
		do
			d = d * 10 + c - '0';
		while (get_c(), !vacant());
		return *this;
	}
	customIN &operator>>(char &d) {
		cueing();
		d = c;
		return *this;
	}
	customIN &operator>>(double &d) {
		scanf("%lf", &d);
		return *this;
	}
	customIN &operator>>(::std::string &d) {
		d.clear();
		cueing();
		do
			d.push_back(c);
		while (get_c(), !vacant());
		return *this;
	}
} IN;
class customOUT {
	int c;
	bool f = 0;
	::std::array<int, 30> buf;
	void put_c(const int x) const { fputc(x, stdout); }

public:
	template <class T>
	auto operator<<(T d) ->
		typename ::std::enable_if<::std::is_signed<T>::value, customOUT &>::type {
		c = 0;
		if (d < static_cast<T>(0))
			f = 1, d = -d;
		while (d)
			buf[c++] = d % 10 + '0', d /= 10;
		if (!c)
			buf[c++] = '0';
		if (f)
			put_c('-'), f = 0;
		while (c--)
			put_c(buf[c]);
		return *this;
	}
	template <class T>
	auto operator<<(T d) -> typename ::std::enable_if<!::std::is_signed<T>::value,
		customOUT &>::type {
		c = 0;
		while (d)
			buf[c++] = d % 10 + '0', d /= 10;
		if (!c)
			buf[c++] = '0';
		while (c--)
			put_c(buf[c]);
		return *this;
	}
	customOUT &operator<<(char d) {
		put_c(d);
		return *this;
	}
	customOUT &operator<<(const ::std::string &d) {
		for (const auto e : d)
			put_c(e);
		return *this;
	}
	customOUT &operator<<(const char *d) {
		while (*d != '\0')
			put_c(*(d++));
		return *this;
	}
	customOUT &operator<<(double d) {
		/*
		printf("%1.9f",d);
		/*/
		printf("%f", d);
		//*/
		return *this;
	}
	void endl() { put_c('\n'); }
	void space() { put_c(' '); }
	operator int() { return 0; }
} OUT;
template <class T = ::std::size_t> T scan() {
	T ret;
	IN >> ret;
	return ret;
}

using int32 = ::std::int_fast32_t;
using int64 = ::std::int_fast64_t;
using uint32 = ::std::uint_fast32_t;
using uint64 = ::std::uint_fast64_t;
using intl32 = ::std::int_least32_t;
using intl64 = ::std::int_least64_t;
using uintl32 = ::std::uint_least32_t;
using uintl64 = ::std::uint_least64_t;

#include <cassert>
#include <utility>

template <class CommutativeMonoid, template <class> class Container>
class fenwick_tree {

public:
	using value_structure = CommutativeMonoid;
	using value_type = typename value_structure::value_type;
	using container_type = Container<value_type>;
	using const_reference = typename container_type::const_reference;
	using size_type = typename container_type::size_type;

private:
	size_type base_size;
	container_type tree;
	static size_type getsize(const size_type size) {
		size_type ret = 1;
		while (ret < size)
			ret <<= 1;
		return ret;
	}

public:
	fenwick_tree() : base_size(0), tree() {}
	explicit fenwick_tree(const size_type size)
		: base_size(getsize(size)), tree(size + 1, value_structure::identity()) {}

	bool empty() const { return size() == 0; }
	size_type size() const { return tree.size() - 1; }

	value_type fold(size_type last) const {
		assert(last <= size());
		value_type ret = value_structure::identity();
		for (; last; last &= last - 1)
			ret = value_structure::operation(tree[last], ::std::move(ret));
		return ret;
	}
	template <class F> size_type search(const F &f) const {
		if (f(value_structure::identity()))
			return 0;
		size_type i = 0, k = base_size;
		value_type acc = value_structure::identity();
		while (k >>= 1)
			if ((i | k) < tree.size() &&
				!f(value_structure::operation(acc, tree[i | k])))
				acc = value_structure::operation(::std::move(acc), tree[i |= k]);
		return i + 1;
	}

	void add(size_type index, const value_type &value) {
		assert(index < size());
		for (++index; index < tree.size(); index += index & ~index + 1)
			tree[index] = value_structure::operation(::std::move(tree[index]), value);
	}
};

template <class T> class plus_monoid {
public:
	using value_type = T;
	static value_type operation(const value_type &x, const value_type &y) {
		return x + y;
	}
	static value_type identity() { return value_type(0); }
	static value_type reverse(const value_type &x) { return x; }
};


#include <algorithm>
#include <utility>
#include <vector>

template <class T> using vec_alias = ::std::vector<T>;

int main() {
	uint32 n;
	IN >> n;
	::std::vector<uint32> a(n);
	for (auto &e : a)
		IN >> e;
	const uint64 mc = static_cast<uint64>(n)*(n + 1) / 4;
	auto less_than = [&n,&a](const uint32 q)->uint64 {
		fenwick_tree<plus_monoid<uint64>, vec_alias> ft(n * 2 + 1);
		ft.add(n, 1);
		uint64 ret = 0;
		uint32 cnt = n;
		for (const auto r : rep(0, n)) {
			if (a[r] < q) {
				++cnt;
			}
			else {
				--cnt;
			}
			ret += ft.fold(cnt);
			ft.add(cnt, 1);
		}
		return ret;
	};


	uint32 low = 0, high = 1000000001;
	while (high - low > 1) {
		uint32 mid = (high + low) / 2;
		if (less_than(mid) > mc)
			high = mid;
		else
			low = mid;
	}
	OUT << low << "\n";
	return 0;
}


Measured memory_bytes: 2560