Nonconsecutive Sort

You are given N integers. Rearrange all of them into a sequence A such that, for every adjacent pair, A[i] + 1 != A[i+1]. In other words, a number must not be followed immediately by the number that is exactly 1 larger.

If several rearrangements satisfy the condition, print the lexicographically smallest one.

The first line contains N, a positive integer not greater than 50.

The second line contains N integers. Each integer is either 0 or a positive integer not greater than 1000.

Print the lexicographically smallest valid sequence on one line, with numbers separated by spaces.