import std.math;
import std.conv;
import std.range;
import std.stdio;
import std.string;
import std.container;
import std.algorithm;

int n;
int[100_001] tree;
int[] a;
int[] s;
long pairs;

void add(int i)
{
    for (; i <= n; i |= i + 1)
        ++tree[i];
}

int get(int r)
{
    int res;
    for (; r >= 0; r = (r & (r + 1)) - 1)
        res += tree[r];
    return res;
}

bool ok(int x)
{
    tree[] = 0;
    foreach(i, val; a) {
        s[i] = val >= x ? 1 : -1;
    }
    auto s1 = cumulativeFold!"a + b"(s);
    int shift = s1.fold!min;
    long t;
    foreach(val; s1.map!(x => x - shift)) {
        add(val);
        t += get(val);
    }
    return t >= (pairs + 1) / 2;
}

void main()
{
    readf("%d\n", &n);
    a = readln.splitter.map!(to!int).array;
    s = new int[a.length];
    pairs = (n * (n + 1)) / 2;
    auto b = a.fold!(min, max);
    int l = b[0];
    int r = b[1];
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (ok(mid))
            l = mid;
        else
            r = mid - 1;
    }
    writeln(l);
}
