Sort Array: Evens First, Odds Later

You are given an array of integers. Your task is to rearrange the array so that all even numbers appear before all odd numbers while preserving the relative order of the even numbers and the odd numbers. An integer ( x ) is considered even if ( x \mod 2 = 0 ), and odd otherwise.

For example, given the array [3, 1, 2, 4, 7, 6], the even numbers are [2, 4, 6] and the odd numbers are [3, 1, 7]. Thus, the output should be [2, 4, 6, 3, 1, 7].

inputFormat

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

outputFormat

Output the modified array with all even numbers at the beginning and odd numbers at the end, preserving their relative orders. The numbers should be separated by a single space.## sample

6
3 1 2 4 7 6

2 4 6 3 1 7