描述

给定一个由N个非负整数组成的序列。我们定义该序列的中位数如下：如果N是奇数，则中位数是序列排序后位于中间的那个元素。注意到在这种情况下，如果序列元素从1开始编号，中位数在排序后的序列中位于第$(N+1)/2$个位置。如果N是偶数，则中位数是两个“中间”元素的半和，即排序后序列中第$N/2$个和第$(N/2)+1$个元素的半和。但原始序列可能是未排序的。

你的任务是编写程序，找到给定序列的中位数。

输入

输入的第一行包含一个整数N，表示序列的长度。序列本身在随后的行中给出，每行一个数字。序列的长度范围在1到250000之间。序列的每个元素是一个不超过$2^{32}-1$的正整数。

输出

你应该输出中位数的值，并精确到小数点后一位。

输入样例 1

4  
3  
6  
4  
5

输出样例 1

4.5  

提示

输入数据量较大，建议使用scanf读取。

来源

1998年乌拉尔大学生程序设计竞赛