Sort Even Before Odd

Given an array of positive integers, reorder the array such that all even numbers appear before all odd numbers. The relative order of the even numbers and odd numbers should remain the same as in the original array. For example, given the array [3, 1, 2, 4], the result should be [2, 4, 3, 1].

This problem requires careful partitioning of the array into two parts while preserving the original ordering within each partition. Mathematically, if we denote the input array as \(a_1, a_2, \dots, a_n\), then we want to output an array where all \(a_i\) such that \(a_i \bmod 2 = 0\) come before all \(a_j\) such that \(a_j \bmod 2 = 1\), preserving their original order.

inputFormat

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

1. The first line contains a single integer \(n\) representing the number of elements in the array.
2. The second line contains \(n\) space-separated positive integers.

outputFormat

Output to standard output (stdout) the reordered array as a sequence of integers separated by a single space. There should be no extra spaces at the beginning or the end of the line.

4
3 1 2 4

2 4 3 1