Reorder Array: Evens First

Given an array of integers, rearrange the elements so that all even numbers appear before all odd numbers while preserving their original order. Formally, for an array \( A \) of length \( n \), partition it into two subsequences \( E \) and \( O \) where \( E \) contains all the even numbers (in the order they originally appear) and \( O \) contains all the odd numbers (in the order they originally appear). The final output is the concatenation \( E \) followed by \( O \).

This problem tests your ability to implement a stable partition of an array based on a given property.

inputFormat

The input is provided via standard input (stdin). The first line contains a single integer \( n \) (which may be zero), representing the number of elements in the array. The second line contains \( n \) space-separated integers.

outputFormat

Output to standard output (stdout) a single line containing \( n \) space-separated integers representing the rearranged array where all evens come before all odds, preserving their original order.

6
1 2 3 4 5 6

2 4 6 1 3 5