fun main(args: Array<String>) {
    Program().solve()
}

class Program {
    fun solve() {
        val sc = MyScanner()
        val n = sc.nextInt()
        val a = sc.intList()
        val all = n.toLong() * (n + 1) / 2
        // 中央値 m以下の値 M/2強 最小

        fun check(l: Long): Boolean {
            var res = 0L
            // l以下の値を1 以外 -1
            // いままでの累積和見る
            // 現在の累積和 - 累積和 > 0の数
            val bit = FenwickTree(2 * n + 1)
            bit.add(n, 1)
            var sum = 0
            for (i in 0 until n) {
                sum += if (a[i] <= l) 1 else -1
                res += bit.sum(sum + n)
                bit.add(sum + n, 1)
            }
            // println("$all $res $l")
            return res * 2 > all
        }

        var ok = 10000000000L
        var ng = 0L
        while (ok - ng > 1) {
            val mid = (ok + ng) / 2
            if (check(mid)) {
                ok = mid
            } else {
                ng = mid
            }
        }
        println(ok)
    }
}

class FenwickTree(private val size: Int) {
    private val tree = Array(size + 1) { 0 }

    // a[i]にnを加算
    fun add(i: Int, n: Int) {
        var t = i + 1
        while (t <= size) {
            tree[t] += n
            t += (t and (-t))
        }
    }

    // [0,i)の合計を求める
    fun sum(i: Int): Int {
        var result = 0
        var t = i
        while (t > 0) {
            result += tree[t]
            t -= (t and (-t))
        }
        return result
    }
}

class MyScanner() {
    private var index = 0
    private var line = listOf<String>()

    fun next(): String {
        while (line.size <= index) {
            line = readLine()!!.split(' ')
            index = 0
        }
        return line[index++]
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextDouble() = next().toDouble()
    fun nextCharArray() = next().toCharArray()
    fun nextChar() = next()[0]

    fun strList(): List<String> {
        index = line.size
        return readLine()!!.split(' ')
    }

    fun intList() = strList().map { it.toInt() }
    fun longList() = strList().map { it.toLong() }
    fun doubleList() = strList().map { it.toDouble() }
}