Cho một mảng a gồm n phần tử là số nguyên. Sắp xếp sao cho số chẵn đứng trước, lẻ đứng sau, chẵn giảm dần, lẻ tăng dần

Đầu vào: Dòng đầu tiên là số lượng phần tử n, dòng tiếp theo là n phần tử của mảng

--

Ràng buộc: 1 <= n <= 1000000; 0 <= a[i] <= 1000000

Đầu ra: In ra mảng đã sắp xếp theo tiêu chí trên

Input:

10
1 2 10 9 6 5 8 7 4 3

Output:

10 8 6 4 2 1 3 5 7 9