Odd-Even Rearrangement

Given an array \(A = [a_1,a_2,\ldots,a_n]\) of integers, rearrange the array so that all odd numbers appear before all even numbers while preserving the relative order of the odd elements and the even elements. In other words, if an element \(a_i\) is odd (i.e. \(a_i \bmod 2 \neq 0\)), it should appear in the odd section of the array in the same order as in the original array, and similarly for even numbers.

Example:

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

inputFormat

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

outputFormat

Output the rearranged array in one line. The odd numbers should appear first, followed by the even numbers. Each number should be separated by a single space.

6
1 2 3 4 5 6

1 3 5 2 4 6