Rearrange Array

You are given an array of distinct integers. Your task is to rearrange the array such that all odd numbers come before all even numbers while preserving the relative order of the odd numbers and the even numbers.

Formally, let \(A = [a_1, a_2, \dots, a_n]\) be the input array. You need to output an array \(B\) such that:

• All odd numbers in \(A\) appear in \(B\) in the same order as they appear in \(A\).
• All even numbers in \(A\) appear in \(B\) in the same order as they appear in \(A\).
• All odd numbers come before any even numbers in \(B\).

For example, if \(A = [4, 3, 2, 7, 8, 1]\), then the output should be \([3, 7, 1, 4, 2, 8]\).

inputFormat

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

outputFormat

Output the rearranged array in one line. The odd numbers should appear first followed by the even numbers, preserving their relative order from the input. The numbers should be separated by a single space.## sample

6
4 3 2 7 8 1

3 7 1 4 2 8