题目描述

给定整数序列 $a_1,a_2,\dots,a_n$。 取出原序列的全部子区间，分别计算每个子区间的中位数；将所有子区间的中位数拼成一个全新序列，输出这个新序列的中位数。

子区间中位数定义

将子区间内数字从小到大排序：

1. 区间长度为奇数：中位数是排序后正中间的数字；
2. 区间长度为偶数：中位数取排序后居中两个数字里更大的那一个。

输入格式

第一行一个整数 $n$，代表原序列长度。 第二行共 $n$ 个整数，为序列 $a_1,a_2,\dots,a_n$。

输出格式

输出一行一个整数：全部子区间中位数构成的新序列的中位数。

数据范围

• $1 \le n \le 10^5$
• $0 \le a_i \le 10^9$