Reorder Heights by Parity

You are given a list of integers representing the heights of individuals. Your task is to reorder the list so that all even numbers appear first followed by all odd numbers, while maintaining the original relative order among the even numbers and among the odd numbers.

Note: Zero is considered an even number.

The problem can be formulated mathematically as follows. Given an array \(A=[a_1, a_2, \dots, a_n]\), produce an array \(B\) such that all even elements appear in the same order as in \(A\) and are positioned before the odd elements which also preserve their original order.

inputFormat

The first line of input contains a single integer \(n\), representing the size of the array.

The second line contains \(n\) space-separated integers representing the heights.

outputFormat

Output the reordered list in a single line. The numbers should be separated by a single space and there should be no trailing spaces.

7
5 8 12 9 3 15 10

8 12 10 5 9 3 15