Cho một mảng các số nguyên.

Hãy sắp xếp các phần tử trong mảng sao cho:

• Các số lẻ đứng trước và được sắp xếp theo thứ tự giảm dần.
• Các số chẵn đứng sau và được sắp xếp theo thứ tự tăng dần.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~N~, là số lượng phần tử của mảng.
• Dòng thứ hai chứa ~N~ số nguyên ~a_i~.

Ràng buộc

• ~1 ≤ N ≤ 10^6~.
• ~1 ≤ a_i ≤ 10^9~.

Kết quả

In ra dãy sau khi đã được sắp xếp theo yêu cầu.

Ví dụ

Dữ liệu vào

10
1 2 3 9 7 4 8 6 10 5

Kết quả

9 7 5 3 1 2 4 6 8 10

Giải thích

Các số lẻ trong mảng là:

~1, 3, 9, 7, 5~

Sau khi sắp xếp giảm dần:

~9, 7, 5, 3, 1~

Các số chẵn trong mảng là:

~2, 4, 8, 6, 10~

Sau khi sắp xếp tăng dần:

~2, 4, 6, 8, 10~

Ghép hai dãy lại theo yêu cầu ta được:

~9, 7, 5, 3, 1, 2, 4, 6, 8, 10~.