Reorder List for Alternating Parity

Given a list of N integers, reorder the list so that no two adjacent elements have the same parity (i.e. one is even and the other is odd) if a strictly alternating arrangement is possible. Otherwise, if a strictly alternating order is impossible, output Not possible.

Note: The integers must be rearranged by following a specific procedure: separate the list into even and odd numbers. If the absolute difference of their counts is more than 1, a strictly alternating order does not exist and you should output Not possible. Otherwise, if the counts are equal or differ by 1, create the result by taking one number from a list in an alternating fashion. If counts are equal, start with an even number; if they differ, start with the group that has more elements.

The output should be the rearranged sequence with each number separated by a single space, or simply the string Not possible if a valid reordering cannot be constructed.

inputFormat

The input is given via standard input with the following format:

N
A1 A2 ... AN

Where N is an integer representing the number of elements in the list, and the second line contains N integers separated by spaces.

outputFormat

Output a single line to standard output. If a strictly alternating parity ordering is possible, output the reordered list as N space-separated integers. Otherwise, output the string Not possible.

6
4 5 2 3 8 9

8 9 2 3 4 5