Reorder Array by Parity Maintaining Relative Order

Given an array of integers, rearrange the array so that all even numbers appear before all odd numbers, while preserving the relative order of the even and odd segments.

For example, if the input array is [3, 1, 2, 4, 5, 6], the rearranged output should be [2, 4, 6, 3, 1, 5]. The solution must read the input from standard input (stdin) and output the result to standard output (stdout).

Formally, let (A = [a_1,a_2,\ldots,a_n]) be the input array. You must rearrange (A) into array (B) such that: [ B = [\text{all even numbers in } A \text{ in order},; \text{all odd numbers in } A \text{ in order}] ] There is no need to sort the even or odd parts; just maintain their original order.

inputFormat

The first line contains a single integer (n) ((n \geq 0)) representing the number of elements in the array. The second line contains (n) integers separated by spaces.

outputFormat

Output a single line containing the rearranged array elements separated by a single space. If (n = 0), output an empty line.## sample

6
3 1 2 4 5 6

2 4 6 3 1 5