Rearrange List to Avoid Adjacent Difference of One

You are given a list of integers. Your task is to rearrange the list so that no two adjacent elements have an absolute difference of exactly 1. If there exists no valid arrangement, output an empty line.

The algorithm should follow these rules:

• If the input list is empty, output an empty line.
• If the input list has one element, output that element.
• Otherwise, sort the list and split it into two halves. Then merge these halves by alternately selecting an element from the larger half and an element from the smaller half.
• Finally, verify that no two consecutive numbers differ by 1. If the check fails, report failure by outputting an empty line.

Mathematically, for a valid arrangement a₁, a₂, ..., a_n, we require that for all i (1 ≤ i < n):

inputFormat

The input is read from standard input. The first (and only) line contains a sequence of integers separated by a single space. If the line is empty, then the list is considered empty.

outputFormat

Output the rearranged list as a sequence of integers separated by a single space in one line. If no valid arrangement exists, output an empty line.

1 3 5 7 9

9 5 7 3 1