Sort Even Numbers Before Odds

Given a list of integers, the task is to sort the list such that all even numbers appear before any odd numbers. Both the even and odd numbers should be sorted in ascending order separately.

Formally, let \(A\) be an input array of \(n\) integers. Define the even subarray \(E = \{a \in A : a \equiv 0 \pmod{2}\}\) and the odd subarray \(O = \{a \in A : a \not\equiv 0 \pmod{2}\}\). The goal is to output the concatenation of the sorted \(E\) and the sorted \(O\), i.e.,

\(\text{result} = sort(E) \Vert sort(O)\)

For example, if the input is 3 1 4 2 5, then the even numbers sorted are 2 4 and odd numbers sorted are 1 3 5. Hence, the final output should be 2 4 1 3 5.

inputFormat

The input is provided via standard input (stdin) in the following format:

1. The first line contains a non-negative integer n — the number of elements in the list.
2. The second line contains n integers separated by spaces.

If n is 0, the second line will be absent.

outputFormat

Output the rearranged list on a single line. The numbers must be separated by a single space. There should be no extra spaces at the beginning or end of the line.

5
3 1 4 2 5

2 4 1 3 5