文件输入输出

本题采用文件输入输出。

• 输入文件：median.in
• 输出文件：median.out

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。

你可以将这个序列任意打乱重排，得到一个新序列 $b_1,b_2,\ldots,b_n$。

定义新序列

其中 $i$ 从 $1$ 开始编号。

将序列 $c$ 从小到大排序，位于第

个位置的元素称为序列 $c$ 的中位数。

请你求出，在序列 $a$ 的所有可能排列方案中，对应序列 $c$ 的中位数的最大值。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示答案。

样例输入 1

5
3 4 7 9 1

样例输出 1

3

样例说明 1

将 $a=[3,4,7,9,1]$ 重排为 $b=[4,7,9,1,3]$，则

排序后序列 $c$ 的中位数为 $3$。

样例输入 2

6
2 6 10 14 20 30

样例输出 2

9

样例输入 3

5
1 5 5 5 10

样例输出 3

3

数据范围

对于所有测试数据：

• $1\le n\le 10^5$；
• $|a_i|\le 10^9$。