ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1306. Медиана последовательности

Ограничение времени: 1.0 секунды
Ограничение памяти: 1 МБ
Ограничение на язык: C, C++, Pascal
Пусть задана последовательность из N целых неотрицательных чисел. Медианой такой последовательности в случае нечетного N называется элемент, который будет равноудален от концов последовательности, если ее отсортировать по возрастанию или убыванию (нетрудно сообразить, что этот элемент имеет номер (N+1)/2 в отсортированной последовательности, если номера считать с единицы). В случае четного N медианой называется среднее арифметическое двух элементов, которые окажутся на местах N/2 и (N/2)+1, если последовательность отсортировать. Однако исходная последовательность не обязана быть отсортированной.
Напишите программу, которая по заданной входной последовательности вычисляет ее медиану.

Исходные данные

В первой строке входа содержится число N — длина последовательности. Во второй и последующих строках расположены сами элементы последовательности, по одному в каждой строке. Длина последовательности — целое число от единицы до 250 000. Каждый элемент последовательности — целое число от 0 до (231−1) включительно.

Результат

Программа должна выдать значение медианы с точностью до одного десятичного знака.

Пример

исходные данныерезультат
4
3
6
4
5
4.5

Замечания

В C++ рекомендуется использовать stdio вместо iostream для экономии некоторого объема памяти.
Источник задачи: II Командный студенческий чемпионат Урала по программированию. Екатеринбург, 3-4 апреля 1998 г.