Sorting in descending order with parity consideration

Kotlin Medium sorting

Task «Sorting in descending order with parity consideration»

Write a program that sorts an array of integers in descending order, but with a special rule: first should come all odd numbers, sorted in descending order, and then all even numbers, also sorted in descending order. Input data: first an integer N (1 ≤ N ≤ 1000) — the number of elements, then N integers. Output the sorted array in one line separated by spaces.

Input Format

First line: integer N (1 ≤ N ≤ 1000). Second line: N integers separated by spaces.

Output Format

One line: sorted numbers separated by spaces.

Examples

Example 1

INPUT

5
3 1 4 2 5

OUTPUT

5 3 1 4 2

Example 2

INPUT

4
2 4 6 8

OUTPUT

8 6 4 2

main.kt