Rearrange Array: Evens Before Odds

You are given an array of integers. Your task is to rearrange the array such that all even numbers appear before all odd numbers while preserving the original order among the even numbers as well as among the odd numbers.

The program should read input from the standard input (stdin) and output the rearranged array to the standard output (stdout). If the array is empty, output an empty line.

Note: The first line of the input contains an integer n (the number of elements in the array). The second line contains n space-separated integers.

inputFormat

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

outputFormat

Output a single line with the rearranged array where all even numbers appear first followed by odd numbers. The numbers should be separated by a space.## sample

6
1 2 3 4 5 6

2 4 6 1 3 5