Trong một vương quốc nọ, các con số đang chuẩn bị tham gia một buổi dạ tiệc hoàng gia. Để buổi tiệc diễn ra trang trọng, Đức vua ban lệnh sắp xếp các con số theo một quy tắc đặc biệt:

• Các con số lẻ (những vị khách danh dự) phải được đứng trước các con số chẵn (những người phục vụ).
• Trong nhóm các số lẻ, các con số phải được sắp xếp theo thứ tự tăng dần.
• Trong nhóm các số chẵn, các con số phải được sắp xếp theo thứ tự giảm dần.

Cho một dãy gồm \(n\) số nguyên \(a_i\), bạn hãy giúp Đức vua sắp xếp lại dãy số này theo đúng quy tắc trên.

Input

• Dòng đầu tiên 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\) (\(1 \le a_i \le 10^6\)).

Output

• In ra dãy số sau khi đã được sắp xếp theo yêu cầu của Đức vua. Các số cách nhau bởi một khoảng trắng.

Example

6
1 4 3 2 5 6

1 3 5 6 4 2

Constraints

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.