Rearrange Even and Odd Numbers

You are given a list of integers. Your task is to rearrange the numbers such that all even numbers appear first followed by all odd numbers. This can be formulated as: $$\text{result} = [\text{even numbers}] + [\text{odd numbers}]$$. If the list is empty, simply output nothing.

Note: The relative order of the even numbers should be preserved, and similarly for the odd numbers.

inputFormat

The first line of input contains an integer n, representing the number of elements in the list. The second line contains n space-separated integers.

outputFormat

Output a single line containing the rearranged list of integers separated by a single space. There should not be any extra spaces at the beginning or end of the line.

4
3 1 2 4

2 4 3 1