Rearrange Even and Odd Numbers

You are given an array of integers. Your task is to rearrange the array so that all even numbers appear before all odd numbers while preserving the relative order of the even numbers and the odd numbers.

For example, if the input array is [4, 3, 1, 2, 5, 8, 7, 6], then the output should be [4, 2, 8, 6, 3, 1, 5, 7].

The problem can be formally described as follows. Given an array \( A = [a_1, a_2, \dots, a_n] \), partition it into two subsequences: the even subsequence \( E \) (where each element satisfies \( a_i \equiv 0 \pmod{2} \)) and the odd subsequence \( O \) (where each element satisfies \( a_i \not\equiv 0 \pmod{2} \)). The final result should be the concatenation of \( E \) followed by \( O \).

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer n, representing the number of elements in the array.
2. The second line contains n space-separated integers.

outputFormat

Print the rearranged array in a single line to stdout, with the numbers separated by a space.

8
4 3 1 2 5 8 7 6

4 2 8 6 3 1 5 7