Rearrange Odds and Evens

You are given a list of integers. Your task is to rearrange the list so that all odd numbers appear before all even numbers, while preserving the relative order of the odd and even numbers from the original list.

More formally, given an array \(A = [a_1, a_2, \dots, a_n]\), you need to construct a new array \(B\) such that all odd elements in \(A\) are placed at the beginning (in the same order as they appear in \(A\)), followed by all even elements of \(A\) (also in the original order).

Input/Output: The input is read from standard input (stdin) and the output should be written to standard output (stdout).

inputFormat

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

outputFormat

Output the rearranged array on a single line, with each number separated by a space.

6
1 2 3 4 5 6

1 3 5 2 4 6