该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Love Median

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

Median plays a very important role in mathematics. Frank has studied the median for a long time. Frank is dazed by a sequence $A$. Frank thinks the problem of finding the median of sequence A is too easy. Now, he's going to make the problem a little bit hard.

First, in this problem, we define the median of a sorted sequence $X$ which length is $N$ as : $X_{\lfloor \frac{1+N+1}{2} \rfloor}$.

Let $n$ be the length of sequence $A$. For each pair $(l,r)$ $(1\leq l\leq r\leq n)$, We make a new array $B$ with $A_l,A_{l+1},...A_r$ and sort it from small to large. Let $m_{l,r}$ be the median of the new array $B$. We will list $m_{l,r}$ for all pairs $(l,r)$ to create a new sequence $M$ and sort it from small to large again. Find the median of $M$.

Input

The first line contains one integers $n(1\leq n\leq 10^5)$.

The second line contains $n$ integers denoting $A_1,A_2,...,A_n$.

Output

Print a single integer, denoting the answer to the question.

3
10 30 20

30

10
5 9 5 9 8 9 3 5 4 3

8

Note

For the first example the new sequence $M$ is $10,30,20,30,30,20$. The median of it after sort is $30$.