Cho dãy số nguyên ~A=(a_0,a_1,…,a_(n-1) )~.

Yêu cầu:

Hãy sắp xếp và in ra các phần tử của dãy A theo yêu cầu sau: Các phần tử chẵn xếp đầu dãy và theo thứ tự không giảm (tăng dần), các phần tử lẻ xếp về cuối dãy và theo thứ tự không tăng (giảm dần)

Dữ liệu:

Dòng 1 chứa số nguyên dương n≤10^5 Dòng 2 chứa n số nguyên dương a0,a1,…,a(n-1) cách nhau bởi dấu cách (∀i:ai≤10^9)

Kết quả:

In ra các phần tử của dãy A sau khi sắp xếp theo yêu cầu theo đúng thứ tự đã sắp cách nhau bởi dấu cách.

Sample Input:

10
1 2 3 4 5 6 7 8 9 2

Sample Output:

2 2 4 6 8 9 7 5 3 1