Rearrange Even Before Odd

You are given an array of integers, and your task is to rearrange the array so that all even numbers appear before all odd numbers. The relative order among even numbers should remain the same as in the original array, and similarly, the relative order among odd numbers should remain unchanged. This problem requires you to read the input from stdin and write the output to stdout.

Formally, given an integer $n$ representing the number of elements in the array and an array of integers, you need to produce a new array in which every even element precedes all odd elements while maintaining their original order. For instance, if the input array is [5, 12, -4, 7, 0, 11, -2, 8], then the expected output should be [12, -4, 0, -2, 8, 5, 7, 11].

inputFormat

The input consists of two lines:

• The first line contains a single integer $n$, the number of elements in the array.
• The second line contains $n$ space-separated integers representing the array elements.

outputFormat

Output a single line containing $n$ space-separated integers which represent the rearranged array with all even numbers appearing before all odd numbers.

## sample

8
5 12 -4 7 0 11 -2 8

12 -4 0 -2 8 5 7 11

</p>