题目描述

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

我们将对长度为 $M$ 的序列 $b$ 的中值定义如下：

• 设 $b'$ 是将 $b$ 按非递减顺序排序后得到的序列。那么， $b'$ 中第 $(M / 2 + 1)$ 个元素的值就是 $b$ 的中位数。这里， $/$ 是整除，向下舍入。

例如， $(10, 30, 20)$ 的中位数是 $20$ ； $(10, 30, 20, 40)$ 的中位数是 $30$ ； $(10, 10, 10, 20, 30)$ 的中位数是 $10$ 。

Snuke 提出了以下问题。

给你一个长度为 $N$ 的序列 $a$ 。对于每一对 $(l, r)$ ( $1 \leq l \leq r \leq N$ )，让 $m_{l, r}$ 成为 $a$ 的连续子序列 $(a_l, a_{l + 1}, ..., a_r)$ 的中位数。我们将 $m_{l, r}$ 列出所有成对的 $(l, r)$ ，从而建立一个新序列 $m$ 。求 $m$ 的中位数。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印 $m$ 的中位数。

样例 #1

样例输入 #1

3
10 30 20

样例输出 #1

30

样例 #2

样例输入 #2

1
10

样例输出 #2

10

样例 #3

样例输入 #3

10
5 9 5 9 8 9 3 5 4 3

样例输出 #3

8

说明

数据规模与约定

• $1 \leq N \leq 10^5$
• $a_i$ 是整数。
• $1 \leq a_i \leq 10^9$

样例 $1$ 解释

$a$ 的每个连续子序列的中值如下：

• $(10)$ 的中位数是 $10$ 。
• $(30)$ 的中位数是 $30$ 。
• $(20)$ 的中位数是 $20$ 。
• $(10, 30)$ 的中位数是 $30$ 。
• $(30, 20)$ 的中位数是 $30$ 。
• $(10, 30, 20)$ 的中位数是 $20$ 。

因此， $m = (10, 30, 20, 30, 30, 20)$ 和 $m$ 的中位数是 $30$ 。