Even-Odd Array Sort

Given an array of integers \(A = [a_1, a_2, \dots, a_n]\), rearrange it so that all even numbers appear before all odd numbers while preserving the relative order among the even numbers and among the odd numbers. For example, if \(A = [1, 2, 3, 4, 5, 6, 7]\), the output should be \([2, 4, 6, 1, 3, 5, 7]\).

Your task is to read the array from standard input and output the rearranged array to standard output. Note that the input may represent an empty array.

inputFormat

The first line contains a single integer \(n\) representing the number of elements in the array. If \(n > 0\), the second line contains \(n\) space-separated integers representing the elements of the array. If \(n = 0\), the second line will be absent.

outputFormat

Output a single line containing the rearranged array with elements separated by a single space. There should be no extra spaces at the beginning or end of the output.

7
1 2 3 4 5 6 7

2 4 6 1 3 5 7