Rearrange Array: Odd and Even Order Preservation

Given an array of integers, your task is to rearrange the array such that all odd numbers appear first followed by all even numbers. The relative order among the odd numbers and the even numbers must be preserved.

For example, if the input is [4, 3, 1, 2, 5] then the output should be [3, 1, 5, 4, 2].

Note: The program should read input from standard input (stdin) and output the result 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. If n is 0, the array is empty.

outputFormat

Output the rearranged array as a single line of space-separated integers. For an empty array, output an empty line.

5
4 3 1 2 5

3 1 5 4 2