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

Например, рассмотрим последовательность {1, 3, 6, 2, 7}. Число 3 является медианой, так как по обе стороны от него находится в точности по два целых числа: {1, 2} и {6, 7}.

Если последовательность содержит четное количество чисел, как например {1, 3, 6, 2, 7, 8}, то одно число не может разбить массив на две равные части, поэтому в качестве медианы будем рассматривать среднее арифметическое центральных чисел {3, 6}. То есть медиана равна (3 + 6) / 2 = 4.5. В задаче Вам следует выводить только целую часть медианы, без дробной. То есть для данного примера ответом будет 4.

Входные данные

Состоит из набора целых чисел x (0 ≤ x < 231), их количество не более 30000.

Выходные данные

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