Bạn được cho một mảng gồm ~n~ phần tử. Hãy sắp xếp mảng sao cho các số chẵn lên đầu và sắp xếp giảm dần, còn các số lẻ ở phía sau theo thứ tự tăng dần.

Input

• Dòng đầu tiên gồm số nguyên ~n~ ~(1 \le n \le 10^3)~ - số lượng các phần tử trong mảng.
• Dòng thứ hai gồm ~n~ phần tử ~a_i~ ~(1 \le a_i \le 10^5)~ - giá trị của phần tử thứ ~i~.

Output

• In ra ~n~ phần tử của mảng sau khi đã sắp xếp.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

4 2 1 3 5