Even-Odd Array Reordering

You are given an array of n integers. Your task is to rearrange the elements of the array such that all even numbers come first, followed by all odd numbers. The relative order among even numbers and odd numbers should remain the same as in the input.

In mathematical terms, an integer x is even if \( x \bmod 2 = 0 \), otherwise it is odd.

inputFormat

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

outputFormat

Output the rearranged array in one line with a space between each number, where all even numbers come first followed by all odd numbers.

9
3 1 2 4 7 6 5 8 9

2 4 6 8 3 1 7 5 9