An muốn sắp xếp lại một dãy số nguyên gồm \(N\) phần tử theo quy luật chẵn lẻ đặc biệt sau:

• Các số chẵn phải xuất hiện trước các số lẻ.
• Các số chẵn được sắp xếp theo thứ tự tăng dần.
• Các số lẻ được sắp xếp theo thứ tự giảm dần.

Hãy giúp An lập trình yêu cầu trên!

Dữ liệu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) cách nhau bởi dấu cách (\(-10^9 \le A_i \le 10^9\)).

Dữ liệu ra

• In ra dãy số thỏa mãn yêu cầu, các số cách nhau bởi dấu cách.

Ví dụ

Đầu vào:

5
1 2 4 3 5

Đầu ra:

2 4 5 3 1

Giải thích: Các số chẵn là 2, 4 sắp xếp tăng dần. Các số lẻ là 1, 3, 5 sắp xếp giảm dần thành 5, 3, 1.