Rearrange Array by Parity and Ascending Order

You are given an array of integers. Your task is to rearrange the array so that all odd numbers appear in ascending order first, followed by all even numbers in ascending order.

Details:

If the input array is empty, the output should be empty as well. You must read the input from stdin and write the result to stdout.

Formally, let \(A\) be the input array. Partition \(A\) into two subarrays \(O\) and \(E\) where:

• \(O = \{x \in A \mid x \text{ is odd}\}\) sorted in ascending order, and
• \(E = \{x \in A \mid x \text{ is even}\}\) sorted in ascending order.

The final output should be the concatenation \(O \Vert E\).

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array.

The second line contains \(n\) space-separated integers denoting the elements of the array.

If \(n = 0\), there will be no numbers on the second line.

outputFormat

Output a single line containing the rearranged array. The numbers should be space-separated. If the array is empty, output an empty line.

## sample

5
9 3 1 5 7

1 3 5 7 9