Rearrange Array: Evens First, Odds Next

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

The problem can be formally stated as follows:

Given an array \( A = [a_1, a_2, \dots, a_n] \), produce an array \( B \) such that all elements \( b_i \) that are even (i.e. \( b_i \mod 2 = 0 \)) appear in the front in the same order as in \( A \), followed by all odd elements in the same relative order as in \( A \).

For example, if \( A = [3, 1, 2, 4] \), then the expected output is \( [2, 4, 3, 1] \).

inputFormat

The input is given in two lines:

• The first line contains an integer \( n \) (the size of the array).
• The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output the rearranged array as a single line of space-separated integers where the even numbers are listed first (in their original order) followed by the odd numbers (in their original order).

## sample

4
3 1 2 4

2 4 3 1

</p>