Even-Odd Rearrangement

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

An integer n is even if \( n \mod 2 = 0 \) and odd otherwise. For example, if the input list is [1, 2, 3, 4, 5], the resulting list should be [2, 4, 1, 3, 5].

If the list is empty, simply output an empty line.

inputFormat

The input is read from standard input (stdin) as follows:

• The first line contains an integer n (0 ≤ n ≤ 10⁵), representing the number of elements in the list.
• The second line contains n space-separated integers.

outputFormat

Output the rearranged list to standard output (stdout) as a single line of space-separated integers. If the list is empty, output an empty line.

5
1 2 3 4 5

2 4 1 3 5