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