Rearrange Array by Parity with Order Preservation

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

In other words, if an element a is even (i.e. \(a \bmod 2 = 0\)) it should appear before any odd element, but both even and odd subarrays should retain their original ordering.

Input Example: If the array is [4, 3, 1, 5, 2, 6], the expected output is [4, 2, 6, 3, 1, 5].

This problem tests your ability to process arrays while preserving the order of certain elements.

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains a single integer n, the number of elements in the array.
• The second line contains n space-separated integers representing the array.

outputFormat

Output the rearranged array to stdout as a sequence of space-separated integers in one line.

6
4 3 1 5 2 6

4 2 6 3 1 5