eolymp
Competitions

Sort & Search

Sort evens and odds

Sequence of integers is given. Sort the given sequence so that first the odd numbers are arranged in ascending order, and then the even numbers are arranged in descending order.

Input

First line contains amount of numbers n (1n1000). Second line contains n integer, each no more than 2 * 109 by absolute value.

Output

Print in one line a sequence of numbers ordered according to the given condition.

Time limit 1 second
Memory limit 128 MiB
Input example #1
7
9 2 3 -6 -5 4 7
Output example #1
-5 3 7 9 4 2 -6