Special Array Sort

You are given an array of n integers. Your task is to sort the array in a special order: all the even numbers should come first in increasing order, followed by all the odd numbers in decreasing order.

Mathematically, let \(E = \{x \in A \mid x \,\%\, 2 = 0\}\) be the set of even numbers and \(O = \{x \in A \mid x \,\%\, 2 \neq 0\}\) be the set of odd numbers. You are required to print the sorted array such that

\(sortedArray = sort_{asc}(E) \cup sort_{desc}(O)\).

Input/Output: The input is read from stdin and the output should be written to stdout.

Example:

Input:
6
5 3 2 8 1 4
Output:
2 4 8 5 3 1

</p>

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 sorted sequence in one line. The even numbers should appear first in increasing order followed by the odd numbers in decreasing order, with each number separated by a space.

## sample

6
5 3 2 8 1 4

2 4 8 5 3 1