Problem Statement

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$.