시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 81 10 9 21.951%

문제

Having a sequence of N integers a1, a2, …, aN, 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 ai+1≠ai+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≤N≤50000) is given. The second line contains N integers a1, a2, …, aN, separated by single spaces. Each integer does not exceed 109 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" (without quotes) if requested sequence does not exist.

예제 입력

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

예제 출력

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

힌트