Rearrange Array with Alternate Parity

You are given an array of n integers. Your task is to rearrange the array such that no two adjacent elements have the same parity (i.e. they are not both even or both odd). In other words, for every adjacent pair (b_i) and (b_{i+1}), the condition (b_i \mod 2 \neq b_{i+1} \mod 2) must hold. If such a rearrangement is not possible, output -1.

Input/Output Format: The input is read from standard input. The first line contains an integer n representing the number of elements. The second line contains n space-separated integers. The output should be printed to standard output: print the rearranged array with space-separated integers, or -1 if no valid arrangement exists.

inputFormat

The first line contains an integer n (1 (\le) n (\le) 10^5), representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Print the rearranged array as space-separated integers such that no two consecutive elements have the same parity. If no valid rearrangement exists, print -1.## sample

6
1 2 3 4 5 6

2 1 4 3 6 5