题目描述

给定一个整数序列 $a_{1}, a_{2}, \dots, a_{n}$，对该序列的所有子区间，分别算出它们的中位数，并且将这些中位数组成一个新序列，输出这个新序列的中位数。

所谓一个序列的中位数，就是将这个序列排序后，排名在最中间的数字；如果序列的长度是偶数，规定中位数是排名最居中的两个数之中偏大的数。

输入格式

• 第一行：一个整数表示 $n$
• 第二行：$n$ 个整数表示 $a_{1}, a_{2}, \dots, a_{n}$

输出格式

一个整数，表示所有子区间中位数组成的新序列的中位数。

3
1 3 2

3

5
17 4 16 1 17

16

数据范围

• 对于 $30\%$ 的数据，$1 \leq n \leq 100$
• 对于 $60\%$ 的数据，$1 \leq n \leq 2,0000$
• 对于 $100\%$ 的数据，$1 \leq n \leq 300,000$
• $1 \leq a_{i} \leq 1,000,000,000$

来源

改编自 ARC101D