Background背景

请对数组进行排序，要求：

奇数在前，偶数在后，奇数部分从小到大排序，偶数部分从大到小排序。

第一排序规则：奇数在前，偶数在后

第二排序规则：奇数从小到大，偶数从大到小

Input输入

输入元素的个数和每个元素的值。

Output输出

奇偶排序的结果。

Samples样例

10
9 6 4 3 5 1 7 10 8 2

1 3 5 7 9 10 8 6 4 2

Limitation限制

1s, 1024KiB for each test case.