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
def d_median_of_medians(N, A):
    class BIT(object):
        """Binary Indexed Tree (1-indexed)"""

        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, index):
            """tree[1]からtree[index]までの和を計算"""
            ret = 0
            while index > 0:
                ret += self.tree[index]
                index -= index & (-index)
            return ret

        def add(self, index, value):
            """tree[index]にvalueを加算"""
            while index <= self.size:
                self.tree[index] += value
                index += index & (-index)

    def is_accepted(x):
        """
        A[l]からA[r]までの要素の中央値がx以上か。すなわち、A[l]からA[r]までの
        要素のうちx以上であるものが (N*(N+1)/2)/2 個以上か
        """
        from itertools import accumulate
        from math import ceil
        a_larger_x = [(1 if a >= x else -1) for a in A]  # x以上か否かを{1, -1}に変換
        cumsum = list(accumulate(a_larger_x))

        ans = 0
        a_larger_x_sorted = {a: k for k, a in enumerate(sorted(cumsum), 1)}
        bit = BIT(N)
        for c in cumsum:
            ans += bit.sum(a_larger_x_sorted[c]) + int(c >= 0)
            bit.add(a_larger_x_sorted[c], 1)
        return True if ans >= ceil((N * (N + 1)) / 4) else False

    # 二分探索の探索区間は [min(A), max(A)] で十分だが、
    # min, maxはO(N)なので、決め打ちしたほうがNが大きなとき速い
    accept = 0
    reject = 10**9 + 1  # 数列の要素の値の制約から、この値は中央値になりえない
    while reject - accept > 1:
        mid = (accept + reject) // 2
        if is_accepted(mid):
            accept = mid
        else:
            reject = mid
    return accept

N = int(input())
A = [int(i) for i in input().split()]
print(d_median_of_medians(N, A))