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

Input is given from Standard Input in the following format:

```
$N$
$a_1$ $a_2$ $...$ $a_N$
```

Print the median of $m$.

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

30

The median of each contiguous subsequence of a is as follows:

• The median of (10) is 10.
• The median of (30) is 30.
• The median of (20) is 20.
• The median of (10, 30) is 30.
• The median of (30, 20) is 30.
• The median of (10, 30, 20) is 20.

Thus, m = (10, 30, 20, 30, 30, 20) and the median of m is 30.