# #P2022A. Love Median

# Love Median

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