Segregate Even and Odd Numbers Maintaining Relative Order

You are given a list of n integers. Your task is to rearrange the list such that all even numbers appear before all odd numbers, while preserving the original relative order within the even numbers and within the odd numbers.

In other words, if the input list is \(a_1, a_2, \ldots, a_n\), you need to output a list \(b_1, b_2, \ldots, b_n\) where all even numbers appear before all odd numbers and if \(a_i\) and \(a_j\) are both even and \(i < j\) then \(a_i\) comes before \(a_j\) in the output list. The same condition holds for the odd numbers.

For example, given the input list:

4 3 2 1 5 6 7

The correct rearranged order is:

4 2 6 3 1 5 7

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \(n\) denoting the number of elements.
• The second line contains \(n\) integers separated by spaces.

If \(n = 0\), the second line may be empty.

outputFormat

Output the rearranged list of numbers on a single line with each number separated by a single space. The output should be written to stdout.

## sample

7
4 3 2 1 5 6 7

4 2 6 3 1 5 7