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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())
a = list(map(int, input().split()))
assert len(a) == N

# 解説を参照
# https://img.atcoder.jp/arc101/editorial.pdf

def mergesort(S, f, t, T=None):
    """f <= i < j <= t かつ S[i] <= S[j] である(i,j)の個数.
       実行後, S[f:t]は整列済みになる."""
    if t - f <= 1:
        return 0

    # 作業スペース
    if T == None:
        T = [0] * len(S)

    mid = (f + t) // 2
    n1 = mergesort(S, f, mid, T)
    n2 = mergesort(S, mid, t, T)

    # マージ
    n = n1 + n2
    i = f
    j = mid
    k = f
    while i < mid:
        if j >= t or S[i] <= S[j]:
            T[k] = S[i]
            i += 1
            n += t - j
        else:
            T[k] = S[j]
            j += 1
        k += 1
    for i in range(f, k):
        S[i] = T[i]
    return n

def n_median_larger_than_or_equal_to(x):
    """aの部分列の中央値のうちx以上のものの個数"""

    # aの要素を -1, 1 に置換したリスト
    b = [-1 if e < x else 1 for e in a]

    # bの累積和
    S = [0]
    for e in b:
        S.append(S[-1] + e)

    # 和が0以上であるbの部分列の個数
    # == i < j and S[i] <= S[j] である(i,j)の個数
    return mergesort(S, 0, len(S))

# 条件を満たす x の最大値を2分探索で探す
lo = 1
hi = max(a)

ncomb = N * (N + 1) // 2    # 部分列の個数

while lo < hi:
    mid = (lo + hi + 1) // 2
    nm = n_median_larger_than_or_equal_to(mid)
    if nm >= (ncomb + 1) // 2:
        lo = mid
    else:
        hi = mid - 1

print(lo)
