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