We will define the median of a sequence b of length M, as follows:

* Let b' be the sequence obtained by sorting b in non-decreasing order. Then, the value of the (M / 2 + 1)-th element of b' is the median of b. Here, / is integer division, rounding down.



For example, the median of (10, 30, 20) is 20; the median of (10, 30, 20, 40) is 30; the median of (10, 10, 10, 20, 30) is 10.

Snuke comes up with the following problem.

You are given a sequence a of length N. For each pair (l, r) (1 \leq l \leq r \leq N), let m_{l, r} be the median of the contiguous subsequence (a_l, a_{l + 1}, ..., a_r) of a. We will list m_{l, r} for all pairs (l, r) to create a new sequence m. Find the median of m.

Constraints

* 1 \leq N \leq 10^5
* a_i is an integer.
* 1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N
a_1 a_2 ... a_N


Output

Print the median of m.

Examples

Input

3
10 30 20


Output

30


Input

1
10


Output

10


Input

10
5 9 5 9 8 9 3 5 4 3


Output

8
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


def median(A):
    return list(sorted(A))[len(A) // 2]


def test(A):
    N = len(A)
    M = []
    for l in range(N):
        for r in range(l + 1, N + 1):
            M.append(median(A[l:r]))
    print(median(M))


def less_than(k):
    arr = [0] * (N + 1)
    for i, b in enumerate(B):
        arr[i + 1] = 1 if b >= k else -1
    cum = cumsum(arr)
    base = min(cum)
    for i in range(len(cum)):
        cum[i] -= base

    # 中央値が k より小さくなる [l, r] の数
    # →[l, r] の総和がマイナスになる組み合わせの数
    # →転倒数
    bit = BinaryIndexedTree(size=max(cum) + 1)
    count = 0
    for i, c in enumerate(cum):
        count += i - bit.sum(c + 1)
        bit.add(c, 1)

        # 中央値が k より小さくなる数が半分より多ければ答えは k より小さい
        # NH2 = (N+1)C2
        if count > (N + 1) * N // 2 / 2:
            return True
    return False


def compress(li, origin=0):
    """
    座圧
    :param li:
    :param int origin:
    :rtype: list of int
    """
    *ret, = map({v: i + origin for i, v in enumerate(sorted(set(li)))}.__getitem__, li)
    return ret


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
# test(A)

indices = argsort(A)

# 座圧
B = compress(A)

lo = 0
hi = N
while abs(lo - hi) > 1:
    mid = (lo + hi) // 2
    if less_than(B[indices[mid]]):
        hi = mid
    else:
        lo = mid
print(A[indices[lo]])
