Three rings for the elven kings
В кузнице Менделеево работает кузнец Келебримбор. Каждый год Келебримбор кует по кольцу и кладет свежескованное кольцо на полку. В конце каждого года к нему приходит Гортхаур, работник Службы Инспекции Менделеево, находит среди колец среднее по массе и записывает его массу в блокнотик (если колец четное число, Гортхаур выбирает из двух средних то, что полегче).
Зная массу каждого кольца, скованного Келебримбором в течение N лет, выясните, как должен выглядеть блокнотик Гортхаура по прошествии этих N лет.
Входные данные
В первой строчке находится число N (1 ≤ N ≤ 1000). Во второй строчке через пробел находится N натуральных чисел, не больших 10000 – веса колец, выкованных Келебримбором в порядке их создания.
Выходные данные
Выведите N чисел через пробел – массы колец, выбранных Гортхауром в порядке выбора.