Nonconsecutive Sort

Rearrange up to 50 integers into the lexicographically smallest sequence where no value is immediately followed by the value one greater than it.

Medium6GreedySortingArraySimulationNo attempts yetTime limit2sMemory limit128 MB

Description

Examples5

Problem

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.

Input

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.

Output

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