Reorder Array: Odds Before Evens

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

Input Format: The first line contains an integer n denoting the number of elements in the array. The second line contains n space-separated integers.

Output Format: Output the reordered array as a sequence of space-separated integers on a single line.

Example:

For the input:

6
1 2 3 4 5 6

The output should be:

1 3 5 2 4 6

The algorithm can be described mathematically as follows:

Given an array \(A = [a_1, a_2, \dots, a_n]\), construct two sequences:

• \(O = [a_i \mid a_i \text{ is odd}]\)
• \(E = [a_i \mid a_i \text{ is even}]\)

Then, the result is \(O \| E\) (i.e. the concatenation of \(O\) and \(E\)).

inputFormat

The input is read from standard input (stdin). The first line contains an integer n representing the number of elements. The second line contains n space-separated integers.

outputFormat

Print the reordered array to standard output (stdout) as space-separated integers on one line.

## sample

6
1 2 3 4 5 6

1 3 5 2 4 6