Sort by Parity

Given an array of n integers, rearrange the array such that all odd numbers appear before all even numbers without changing the relative order of the numbers. Formally, if we denote by \(O\) the sequence of odd numbers and \(E\) the sequence of even numbers (each preserving their original order), then the required output is the concatenation \(O \Vert E\).

inputFormat

The first line contains an integer \(n\) (\(0 \le n \le 10^5\)).

The second line contains \(n\) integers separated by spaces.

outputFormat

Output the rearranged list of integers in one line, with each number separated by a single space.

7
3 8 5 13 6 12 5

3 5 13 5 8 6 12