import std.stdio, std.algorithm, std.range, std.conv, std.string, std.math, std.container, std.typecons;
import core.stdc.stdio;
// foreach, foreach_reverse, writeln

class BIT {
	int[] data;
	this(int n) {
		data = new int[n+1];
	}
	BIT dup() {
		BIT ret = new BIT(to!int(data.length));
		ret.data = data.dup;
		return ret;
	}
	void add(int i, int x=1) {
		i++;
		while (i < data.length) {
			data[i] += x;
			i += i&-i;
		}
	}
	int sum(int i) {
		int ret = 0;
		i++;
		while (i) {
			ret += data[i];
			i -= i&-i;
		}
		return ret;
	}
}

void main() {
	int n;
	scanf("%d", &n);
	int[] a = new int[n];
	foreach (i; 0..n) scanf("%d", &a[i]);
	long L = long(n+1)*n/2;
	long M = (L+1)/2;
	int l = 0, u = (1<<30)-10;
	long count(int[] b) {
		int s = n;
		long ret = 0;
		BIT c = new BIT(n*2+1);
		foreach (i; 0..n) {
			c.add(s);
			s += b[i];
			ret += c.sum(s);
		}
		//writeln(b); writeln(ret);
		return ret;
	}
	while (l+1 < u) {
		int m = (l+u)/2;
		int[] b = new int[n];
		foreach (i; 0..n) {
			b[i] = a[i]<m ? -1 : 1;
		}
		if (count(b) < M) u = m; else l = m;
	}
	writeln(l);
}