Stable Partition: Evens First, Odds Later

Given an array of n integers, rearrange the array so that all even numbers appear before all odd numbers. The relative order of the even numbers should stay the same, and likewise for the odd numbers.

Mathematically, if the input array is denoted by \(A = [a_1, a_2, \dots, a_n]\), you must compute an output array \(B\) such that:

\[ B = \text{evens}(A) \mathbin+ \text{odds}(A), \]

where \(\text{evens}(A)\) is the subarray of all \(a_i\) with \(a_i \equiv 0 \pmod{2}\), and \(\text{odds}(A)\) is the subarray of all \(a_i\) with \(a_i \not\equiv 0 \pmod{2}\), both preserving their original order.

Your solution should read the input from stdin and write the output to stdout.

inputFormat

The first line contains an integer \(n\) which indicates the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

Output the rearranged array as a sequence of space-separated integers on one line.

7
3 8 6 5 2 7 4

8 6 2 4 3 5 7