Weird Sort

Time limit1sMemory limit128 MB

Summary

Reorder N integers so no element equals the previous element plus one, outputting the lexicographically smallest valid ordering or No solution.

Level: Medium7 of 10
Topics: Greedy, Sorting, Math, Implementation
Solved: No attempts yet

Problem

You are given a sequence of $N$ integers $a_1, a_2, \dots, a_N$ . Reorder them so that no element is exactly one greater than the element immediately before it. Formally, the final sequence must satisfy $a_{i+1} \neq a_i + 1$ for every $i$ with $1 \le i < N$ .

If several orderings satisfy this condition, output the lexicographically smallest one.

Input

The input consists of several data sets. Each data set spans two lines. The first line contains the sequence length $N$ ( $1 \le N \le 50000$ ). The second line contains $N$ integers $a_1, a_2, \dots, a_N$ separated by single spaces, each satisfying $|a_i| \le 10^9$ . A line containing a single $0$ marks the end of the input and is not processed.

Output

For each data set, print the resulting sequence on its own line, with integers separated by single spaces. If no valid ordering exists, print No solution instead.

Examples3

Example 1

Input

2
1 2
6
1 2 3 4 5 6
6
1 1 2 2 3 3
0

Expected output

2 1
1 3 2 4 6 5
1 1 3 3 2 2

Example 2
Input
```
1
5
0
```
Expected output
```
5
```
Example 3
Input
```
3
1 2 4
0
```
Expected output
```
1 4 2
```