Under construction

Still being built. Things may change

MEXchange

Interview

Time limit1sMemory limit1024 MB

Summary
Given the prefix MEX sequence B, construct a permutation A that produces B, or report that no such permutation exists.
Level

Medium5 of 10

Topics
Greedy, Implementation
Solved
No attempts yet

Problem

A permutation of length NN is a sequence in which each integer from 11 to NN appears exactly once. For example, [2,3,1,5,4]\left[ 2,3,1,5,4 \right] is a permutation, but [1,2,2]\left[ 1,2,2 \right] is not, because 22 appears twice. Also, [1,3,4]\left[ 1,3,4 \right] has length 33 but is not a permutation, because it contains 44.

Given a permutation AA of length NN, define the sequence BB as follows.

Bi=MEX⁡({A1,A2,⋯ ,Ai}) (1≤i≤N)B_i=\operatorname{MEX}\left( \{A_1,A_2,\cdots ,A_i\} \right)\ (1 \leq i \leq N)

Given a sequence BB of length NN, find the permutation AA.

MEX⁡(S)\operatorname{MEX}\left( S \right) is the smallest positive integer not contained in the set SS. For example, MEX⁡({1,2,5})=3\operatorname{MEX}\left(\{ 1,2,5 \}\right) =3 and MEX⁡({2,3,4})=1\operatorname{MEX}\left(\{ 2,3,4 \}\right) =1. Note that the MEX⁡\operatorname{MEX} defined in this problem can never be 00.

Input

The first line contains the length NN of the permutation AA. (3≤N≤200 000)\left( 3\leq N\leq 200\,000 \right)

The second line contains NN integers BiB_i, separated by spaces, which are the elements of the sequence BB. (1≤Bi≤N+1)\left( 1\leq B_i\leq N+1 \right)

Output

On the first line, print Yes if a permutation AA that produces BB exists, and No otherwise.

If it exists, print the elements of the permutation AA on the second line, separated by spaces. If there are multiple answers, print any of them.

Examples2

  1. Example 1

    Input
    5
    1 2 2 2 6
    
    Expected output
    Yes
    3 1 4 5 2
    
  2. Example 2

    Input
    5
    1 4 4 4 6
    
    Expected output
    No