Rearrange Even and Odd Numbers

Given an array of integers, rearrange the array so that all even numbers appear before the odd numbers, while preserving the relative order among even and odd numbers.

In mathematical terms, for every integer \(a\), if \(a \bmod 2 = 0\) then it is even, otherwise it is odd. Your goal is to output the rearranged array where all even numbers come first followed by all odd numbers.

Example:

Input: 7
       4 3 2 1 5 6 7
Output: 4 2 6 3 1 5 7

Note: The input is provided via standard input (stdin) and the output must be printed to standard output (stdout).

inputFormat

The first line contains an integer (N), representing the number of elements in the array. The second line contains (N) space-separated integers.

outputFormat

Output the rearranged array in one line, with even numbers first and odd numbers later, separated by a single space.## sample

7
4 3 2 1 5 6 7

4 2 6 3 1 5 7