题目描述

我们一般把一组数中大小处于正中间的数叫做“中位数”。

对这组数的个数 $n$，若 $n$为奇数，则中位数为从小到大排序后正中间的那个。例如：5 个数 3, 4, 1, 9, 6 排序后为 1, 3, 4, 6, 9，中位数为 4；

若 $n$为偶数，会有两个数在正中间，这时中位数规定为这两个数的平均值。例如：6 个数 2, 4, 9, 8, 6, 5，排序后 为 2, 4, 5, 6, 8, 9，中位数为 5, 6 的平均值 5.5。

对一组数，你需要找出它们的中位数，并以指定格式输出。

输入格式

输入共 2 行：

第 1 行，1 个正整数 $n$，为数的个数；

第 2 行，用空格隔开的 $n$个正整数 $a_1, a_2, ..., a_n$。

输出格式

输出共 1 行：

第 1 行，1 个数，为 $a_1, a_2, ..., a_n$的中位数，若不是整数则保留一位小数。

5
3 4 1 9 6

4

数据规模与约定

$1 \le n \le 300000$

$1 \le a_1, a_2, ..., a_n \le 10^9$