Array Odd-Even Sort

You are given an array of integers. Your task is to rearrange the array such that all the odd numbers are sorted in ascending order and come first, followed by all the even numbers sorted in descending order.

More formally, given an array \(A\) of \(n\) integers, construct a new array \(B\) by performing the following steps:

1. Extract all odd elements from \(A\) and sort them in increasing order.
2. Extract all even elements from \(A\) and sort them in decreasing order.
3. Concatenate the sorted odd elements with the sorted even elements.

For example, if the input is [5, 3, 2, 8, 1, 4], the output should be [1, 3, 5, 8, 4, 2].

inputFormat

The first line contains an integer \(n\) denoting the number of elements in the array.

The second line contains \(n\) space-separated integers.

outputFormat

Print the rearranged array as a sequence of space-separated integers on one line.

6
5 3 2 8 1 4

1 3 5 8 4 2