Cho dãy số \(A\) có \(n\) phần tử \(a_{1}, a_{2}, a_{3}, a_{4},..,a_{n}\). Hãy sắp xếp các số chẵn trong dãy theo thứ tự tăng dần và các số lẻ theo thứ tự giảm dần.
In ra dãy kết quả đã sắp xếp, trong đó vị trí số chẵn và vị trí số lẻ không thay đổi so với dãy ban đầu.

Input

• Dòng đầu ghi số \(n\) \((1 \leq n \leq 1000)\).
• Các dòng tiếp theo ghi đủ \(n\) số của dãy \(A\), các số đều nguyên dương và không quá \(1000\).

Output

• Gồm \(1\) dòng duy nhất là dãy kết quả đã sắp xếp, trong đó các vị trí của số chẵn và số lẻ không thay đổi.

Example

10
1 2 3 4 5 6 7 7 9 6

9 2 7 4 7 6 5 3 1 6