Rearrange Array: Evens Before Odds

Given an array of integers, rearrange the array such that all even numbers appear before any odd numbers. The relative order among the even numbers and among the odd numbers must remain unchanged. In other words, if \( E \) is the list of even numbers in their original order and \( O \) is the list of odd numbers in their original order, then the answer should be \( E \, \| \, O \) (where \(\|\) denotes concatenation).

If the array is empty or contains only even or only odd numbers, simply output the array as is.

inputFormat

Input is read from standard input (stdin). The first line contains an integer \( N \) denoting the number of elements in the array. The second line contains \( N \) space-separated integers representing the elements of the array.

outputFormat

Output the rearranged list to standard output (stdout) as a single line of space-separated integers.

7
4 1 3 2 6 5 8

4 2 6 8 1 3 5