0168. The Middlest Number

Input file name:	midnum.in
Output file name:	midnum.out
Time limit:	1 s
Memory limit:	64 megabytes

One can perform the following operations to get the middlest number of a given sequence a₁, a₂, …, a_n written on the blackboard. He must select the minimal number a_min, the maximal number a_max, erase them and write down (a_min+a_max)/2. After repeating this n-1 times, there will be only one number on the blackboard. We will call it the middlest number.

Your task is to find the middlest number of a given sequence of integers.

Input file

The first line contains integer 1 ≤ n ≤ 239017. The next n lines contain numbers a_i.

Output file

Output the middlest number of the given sequence with six digits after the decimal point.

Examples:

midnum.in	midnum.out
3 2 3 9	4.250000

Source: Petrozavodsk Summer 2003. KOTEHOK's Contest, Sunday, August 31
Author: Andrew Lopatin

Discuss       Submit a solution



Printable version