Even-Odd Array Rearrangement

You are given an array of n integers. Rearrange the array such that all even numbers appear before all odd numbers, while preserving the relative order of even numbers amongst themselves and odd numbers amongst themselves.

Formally, let \( A = [a_1, a_2, \dots, a_n] \). You need to reorder it into \( B = [b_1, b_2, \dots, b_n] \) satisfying:

\( B = [ \text{all even elements of } A \text{ in the same order}, \; \text{all odd elements of } A \text{ in the same order} ] \).

For example, if the input array is [3, 1, 2, 4], the rearranged array should be [2, 4, 3, 1].

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains a single integer \( n \) (where \( 0 \leq n \leq 10^5 \)), the number of elements in the array.
• The second line contains \( n \) space-separated integers.

outputFormat

Output to standard output (stdout) the rearranged array as a sequence of space-separated integers in one line.

4
3 1 2 4

2 4 3 1