Sequence Median（http://noi.openjudge.cn/ch0401/1625/）

描述

Given a sequence of N nonnegative integers. Let's define the median of such sequence. If N is odd the median is the element with stands in the middle of the sequence after it is sorted. One may notice that in this case the median has position (N+1)/2 in sorted sequence if sequence elements are numbered starting with 1. If N is even then the median is the semi-sum of the two "middle" elements of sorted sequence. I.e. semi-sum of the elements in positions N/2 and (N/2)+1 of sorted sequence. But original sequence might be unsorted.

Your task is to write program to find the median of given sequence.

输入

The first line of input contains the only integer number N - the length of the sequence. Sequence itself follows in subsequent lines, one number in a line. The length of the sequence lies in the range from 1 to 250000. Each element of the sequence is a positive integer not greater than 2^32 - 1 inclusive.

输出

You should print the value of the median with exactly one digit after decimal point.

描述

给出一个有N个非负整数的序列。定义这个序列的中位数。如果N是奇数，那么中位数则是排序后的序列中位于中间的那个元素。通过这个样例可以发现，如果序列中元素的序号是从1开始，中位数在已排序的序列中的位置是（N+1）/2.如果N是偶数，那么中位数是已排序的序列中位于中间的两个元素的和的一半，即已排序的序列中位于N/2和（N/2）+1的元素的和的一半。但是初始序列可能无序。

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

输入

第一行输入只包括一个整数N——序列的长度。序列本身跟随在后续行，每个数字占用一行。序列长度的范围在1到250000之间。序列中的每个元素都是不大于2^32-1的正整数。

输出

你应该打印出由一位小数的中间值。