Even-Odd Array Rearrangement

Given an array of integers, rearrange the array such that all even numbers come before all odd numbers, while maintaining the relative order of the numbers as they appear in the original array.

In other words, if an integer x satisfies \(x \equiv 0 \pmod{2}\) it is even, otherwise it is odd. The even numbers should appear in the same order as in the input, followed by the odd numbers in their original order.

For example, given the array [1, 2, 3, 4, 5, 6], the output should be [2, 4, 6, 1, 3, 5].

Your solution should efficiently process inputs, as the number of elements can be large (up to 100,000 elements).

inputFormat

The first line contains a single integer n (0 ≤ n ≤ 100,000) representing 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 array in a single line with the elements separated by spaces. If the array is empty, output nothing.

6
1 2 3 4 5 6

2 4 6 1 3 5