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
from itertools import accumulate
import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size + 1)
        self.size = size

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

N = int(input())
a = list(map(int, input().split()))
lb, ub = -1, 10**9
while ub - lb > 1:
    m = (lb + ub) // 2
    b = [0] * (N+1)
    for i in range(N):
        if a[i] <= m:
            b[i+1] = 1
    b = list(accumulate(b))
    # b[j+1] - b[i] > (j+1)//2 - i//2
    # b[j+1] - (j+1)//2 > b[i] - i//2
    bit_odd = BIT(2*N)
    bit_even = BIT(2*N)
    cnt = 0
    for i in range(N):
        x = N + b[i+1] - i//2 - 1
        y = N + b[i+1] - (i+1)//2 - 1
        if i % 2 == 0:
            bit_even.add(N + b[i] - i//2, 1)
            cnt += bit_even.sum(x) + bit_odd.sum(y)
        else:
            bit_odd.add(N + b[i] - i//2, 1)
            cnt += bit_even.sum(y) + bit_odd.sum(x)
    if cnt < N*(N+1)//4 + 1:
        lb = m
    else:
        ub = m
print(ub)