Problems
Three rings for the elven kings
Three rings for the elven kings
В кузнице Менделеево работает кузнец Келебримбор. Каждый год Келебримбор кует по кольцу и кладет свежескованное кольцо на полку. В конце каждого года к нему приходит Гортхаур, работник Службы Инспекции Менделеево, находит среди колец среднее по массе и записывает его массу в блокнотик (если колец четное число, Гортхаур выбирает из двух средних то, что полегче).
Зная массу каждого кольца, скованного Келебримбором в течение \textbf{N} лет, выясните, как должен выглядеть блокнотик Гортхаура по прошествии этих \textbf{N} лет.
\InputFile
В первой строчке находится число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{1000}). Во второй строчке через пробел находится \textbf{N} натуральных чисел, не больших \textbf{10000} -- веса колец, выкованных Келебримбором в порядке их создания.
\OutputFile
Выведите \textbf{N} чисел через пробел -- массы колец, выбранных Гортхауром в порядке выбора.
Input example #1
1 1
Output example #1
1