Sort Even Descending and Odd Ascending

You are given a list of integers. Your task is to sort the even numbers in descending order and the odd numbers in ascending order, then concatenate the sorted even numbers followed by the sorted odd numbers.

In mathematical terms, let \(E\) be the set of even numbers and \(O\) be the set of odd numbers from the list. You must output the list

[ sorted(E){\text{desc}} ; | ; sorted(O){\text{asc}} ]

where \(|\) denotes concatenation.

inputFormat

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

outputFormat

Output a single line containing the sorted list. The even numbers should appear first in descending order, followed by the odd numbers in ascending order. Each number should be separated by a space.

## sample

7
3 1 4 9 2 7 6

6 4 2 1 3 7 9

</p>