Special Sort

This problem consists of two parts. In the first part, you are required to implement a function to check whether a given number is a prime number. A prime number is defined as a natural number greater than 1 that has no positive divisors other than 1 and itself.

In the second part, using the prime checking function, you must rearrange a sequence of integers according to the following rules:

• All prime numbers should come first in ascending order.
• All non-prime numbers should follow in descending order.

For example, given the sequence [4, 7, 9, 5, 2, 10] with n = 6, the rearranged sequence will be [2, 5, 7, 10, 9, 4].

inputFormat

The first line of input contains an integer n, which represents the number of elements in the sequence. The second line contains n space-separated integers.

outputFormat

Output the rearranged sequence in a single line, with the numbers separated by a space.## sample

6
4 7 9 5 2 10

2 5 7 10 9 4