Найти медиану - 2

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

Например, рассмотрим последовательность $\{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\le x<2^{31})$, их количество не более $10^6$.

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

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

Примеры