Migrated from Lutece 1063 秋实大哥与妹纸

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

致中和，天地位焉，万物育焉。秋实大哥是一个追求中庸的人。

虽然秋实大哥的仰慕者众多，但秋实大哥不喜欢极端的妹纸。所以他想从所有仰慕自己的妹纸中挑选出一个符合中庸之道的。

每一个妹纸对秋实大哥的仰慕程度可以用一个整数$a_i$来表示，秋实大哥想要找出这些数的中位数。

计算有限个数的数据的中位数的方法是：

把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数，则中间那个数据就是这群数据的中位数； 如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数。

Input

第一行有一个整数$n$，表示秋实大哥的仰慕者数目。

接下来$n$行，每行有一个正整数$a_i$。

$1\leq n\leq 250000$，$1\leq a_i < 2^{31}$。

Output

输出这$n$个数的中位数，保留一位小数。

Samples

3
1
2
3

2.0

Note

注意内存大小限制。

Resources

2015 UESTC Training for Data Structures