    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;
        }
        foreach (i; iota(n - 1))
          s[i + 1] += s[i];
        //int shift = s.fold!min;
        int shift = 1000000000;
        foreach(val; s)
          shift = min(shift, val);
        long t;
        foreach (val; s.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];
        int l = a[n - 1];
        int r = a[n - 1];
        foreach (i; iota(n - 1)) {
          r = max(r, a[i]);
          l = min(l, a[i]);
        }
        
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (ok(mid))
                l = mid;
            else
                r = mid - 1;
        }
        writeln(l);
    }
