Background背景

将一个数组分成前半部分奇数、后半部分偶数，并将前后两部分各自从小到大排序。

Input输入

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

Output输出

奇偶排序的结果

Samples样例

10
9 6 4 3 5 1 7 10 8 2

1 3 5 7 9 2 4 6 8 10

Limitation限制

1s, 1024KiB for each test case.