Reorder Even and Odd

You are given a list of integers. Your task is to reorder the list so that all the even numbers appear before all the odd numbers while maintaining the original relative order among the even numbers and among the odd numbers.

In other words, if the input list is \(a_1, a_2, \dots, a_n\), you should produce a list such that all even numbers appear first (in the same order as they appeared in the input) followed by all odd numbers (again in the same order as they appeared in the input).

Example: For the input [3, 1, 2, 4], the output should be [2, 4, 3, 1] because 2 and 4 are even and maintain order, and 3 and 1 are odd and maintain their order.

inputFormat

The first line of the input contains a single integer \(n\) representing the number of elements in the list. The second line contains \(n\) space-separated integers.

outputFormat

Output the reordered list as a sequence of space-separated integers on a single line. There should be no extra spaces at the beginning or the end of the line.

4
3 1 2 4

2 4 3 1