Знайти медіану - 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$.

Вихідні дані

Для кожного вхідного числа в окремому рядку вивести медіану поточної послідовності. Для кожного значення медіани слід виводити лише її цілу частину.

Приклади