题目描述

我们将一个长度为 $M$ 的序列 $b$ 的中位数定义为：将序列 $b$ 按照非降序排序之后，第 $(M / 2 + 1)$ 个元素，其中 $M / 2$ 向下取整。

王老师现在向你发起挑战。王老师会给你一个长度为 $N$ 的序列 $a$，对于每一个二元组 $(l, r)(1 \le l \le r \le N)$，$m_{l, r}$ 表示序列 $a$ 的连续子序列 $(a_l, a_{l + 1}, a_{l + 2}, ..., a_r$ 的中位数，将所有的 $m_{l, r}$ 构成一个新序列 $m$，请你求出序列 $m$ 的中位数。

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个正整数 $a_i$，表示给定的序列 $a$。

$1 \le N \le 10^5$，$1 \le a_i \le 10^9$。

输出格式

序列 $m$ 的中位数。

3
10 30 20

30

1
10

10

10
5 9 5 9 8 9 3 5 4 3

8