Відсортуйте масив з \(N\) чисел так щоб спочатку йшли всі парні за зростанням від меншого до більшого, потім всі непарні за спаданням від більшого до меншого).

Формат вхідних даних

В першому рядку \(N\) (\(1 \le N \le 10^5\)).
В наступному рядку \(N\) чисел \(Ai\) (\(10^9 \le Ai \le 10^9\))

Формат вихідних даних

Виведіть відсортований масив.

Приклад вхідних даних

8
-45 -32 23 -17 14 -10 99 82

Приклад вихідних даних

-32 -10 14 82 99 23 -17 -45