Alternate Even-Odd Permutation

You are given a list of integers. Your task is to rearrange the list so that the elements alternate between even and odd numbers.

If multiple rearrangements meet the conditions, you must return the lexicographically smallest one. Formally, among all valid rearrangements, let \(a = [a_1, a_2, \dots, a_n]\) and \(b = [b_1, b_2, \dots, b_n]\); then \(a\) is lexicographically smaller than \(b\) if there exists an index \(i\) such that \(a_j = b_j\) for all \(1 \le j < i\) and \(a_i < b_i\).

If it is not possible to alternate (i.e. if \(|\text{#evens} - \text{#odds}| > 1\)), return the sorted list.

inputFormat

The input is given via standard input. The first line contains a single integer \(n\) (the number of integers). The second line contains \(n\) space-separated integers representing the list.

\(1 \le n \le 10^5\) (for example).

outputFormat

Output the rearranged list as a sequence of space-separated integers on a single line. The output should be printed to standard output.

4
1 2 3 4

2 1 4 3