Odd-Even Sorting

You are given an array of non-negative integers. Your task is to reorder the array such that all odd numbers appear before all even numbers, while maintaining the relative order of odd numbers among themselves and even numbers among themselves.

Formally, let \(A = [a_1, a_2, \dots, a_n]\) be the input array. You need to output an array \(B\) where all \(a_i\) such that \(a_i \bmod 2 \neq 0\) appear in the same order as in \(A\), followed by all \(a_i\) such that \(a_i \bmod 2 = 0\) in their original order.

The input is given as follows:

• The first line contains an integer \(n\) indicating the number of elements.
• The second line contains \(n\) space-separated non-negative integers.

The output should be a single line containing the rearranged array with each value separated by a space.

inputFormat

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

outputFormat

Output a single line containing the rearranged array where all odd numbers precede all even numbers. The relative order of odd numbers and even numbers should be maintained.

5
3 1 4 2 5

3 1 5 4 2