Problem #2825 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

Having a sequence of $N$ integers $a_{1}, a_{2}, \dots, a_{N}$ , you need to order them in a way when no two consecutive integers have consecutive values. In other words, for all $i$ , where $0 < i < N$ , condition $a_{i} + 1 \neq a_{i + 1}$ should be satisfied for the final sequence.

If more than one sequence satisfying this condition exists, lexicographically minimal one should be found.

输入格式

The input file consists of several data sets. In the first line of each set the sequence length $N$ $(1 \leq N \leq 50000)$ is given. The second line contains $N$ integers $a_{1}, a_{2}, \dots, a_{N}$ , separated by single spaces. Each integer does not exceed $10^{9}$ in its absolute value. The value $N = 0$ indicates the end of the input file.

输出格式

For each data set you need to print result sequence in separate line. Integers in the sequence must be separated by single spaces. Print No solution if requested sequence does not exist.

样例

Input

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

Output

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

4 人解决，15 人已尝试。

6 份提交通过，共有 54 份提交。

8.9 EMB 奖励。

创建: 14 年，6 月前.

修改: 7 年，6 月前.

最后提交: 3 年前.

来源: Ukrainian

2825. Weird sort

输入格式

输出格式

样例

服务

开源

关于我们