题目描述

你的手头有一个长度为 $N$ 的序列 $A$。

你需要求出所有非空连续子段的中位数组成的序列的中位数。

说明：在此题中，若某个待求解中位数的序列的长度 $l$ 是偶数，那么中位数是序列中从小到大排序第 $\frac{l}{2}+1$ 个数。

输入格式

第一行为一个数 $N$。

第二行为序列 $A$ 的所有元素。

输出格式

按照题目要求输出，只有一个数。

3
10 30 20

30

1
10

10

10
5 9 5 9 8 9 3 5 4 3

8

数据范围

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ a_i\ \leq\ 10^9$