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

Напишите программу, которая по заданной входной последовательности вычисляет ее медиану.

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

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

В C++ рекомендуется использовать stdio вместо iostream для экономии некоторого объема памяти.