0168. The Middlest Number

Имя входного файла:	midnum.in
Имя выходного файла:	midnum.out
Ограничение по времени:	1 s
Ограничение по памяти:	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

Источник: Petrozavodsk Summer 2003. KOTEHOK's Contest, Sunday, August 31
Автор: Andrew Lopatin

Обсудить       Отправить решение



Версия для печати