Ouroboros sequence P87670

Statement

0.6 The ouroboros is an ancient symbol depicting a snake eating its own tail.

We will call a sequence of $n$ numbers $x_1$ … $x_n$ an ouroboros if two things happen:

For every $1 \le i < n$ , $x_i$ and $x_{i+1}$ differ by one.
$x_n$ and $x_1$ also differ by one.

For instance, 3 4 5 4 3 2 1 2 is an ouroboros sequence, while 3 4 5 4 3 is not.

0.4

Given a sequence of numbers, can you decide if they can be rearranged to form an ouroboros sequence?

Input

Input consists of several cases, each with $n$ , followed by $x_1$ … $x_n$ . Assume $2 \le n \le 10^5$ , and that each $x_i$ is an integer number between 0 and 1000.

Output

Print one line for each case. If it is not possible to build an ouroboros sequence from the given numbers, print “NO”. Otherwise, print “YES” followed by the lexicographically largest ouroboros sequence.

Public test cases

Input

8  3 4 5 4 3 2 1 2
5  3 4 5 4 3
2  1000 0
4  2 1 1 0
6  9 9 8 9 8 8
6  9 11 9 10 8 10
8  2 2 3 3 4 4 2 3
8  2 1 2 1 2 1 2 4

Output

YES 5 4 3 2 1 2 3 4
NO
NO
YES 2 1 0 1
YES 9 8 9 8 9 8
YES 11 10 9 8 9 10
NO
NO

Information

Author: Joan Alemany
Language: English
Official solutions: C++
User solutions: C++