Ouroboros sequence P87670


Statement
 

pdf   zip

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

We will call a sequence of n numbers x1 …⁠ ⁠xn an ouroboros if two things happen:

  1. For every 1 ≤ i < n, xi and xi+1 differ by one.
  2. xn and x1 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.

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 x1 …⁠ ⁠xn. Assume 2 ≤ n ≤ 105, and that each xi 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++