Задача C. Глубина движения по траектории

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

Исследователи морских глубин хотят рассчитать среднюю глубину траектории движения глубоководного аппарата для того, чтобы оценить, какой аппарат необходимо приобрести для мониторинга ареала обитания моллюсков. Им известны контрольные точки, где он должен проводить измерения и глубина океанского дна в этих точках. Помогите им написать программу, определяющую медиану значений глубины.

Примечание. Медианой xmed последовательности чисел называется такое из них, что 50% значений последовательности меньше либо равно медиане, а оставшиеся 50% - больше либо равны медиане. Например, допустим, имеется отсортированный массив длины n, нумерация элементов начинается с 1. Тогда xmed = x((n + 1) / 2), в случае, если число n - нечетно. Если n - четно, то медиана равна: xmed = (x(n / 2) + x(n / 2 + 1) / 2).

Формат входных данных

Первая строка входных данных содержит целое положительное число N - число контрольных точек, где аппарату необходимо выполнить измерения. Во второй строке записаны все элементы массива, разделённые пробелами, - глубина дна в контрольных точках.

Формат выходных данных

Программа должна вывести медиану последовательности глубин с точностью до двух знаков после запятой. Округление должно выполняться по правилам математики.

Ограничения

1 ≤ N ≤ 105

0 ≤ ai ≤ 104, где ai - элемент массива

Примеры тестов

Стандартный вход Стандартный выход
1
5
3 5 1 2 4
3.00
2
6
3 5 1 6 2 4
3.50

0.138s 0.028s 13