만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

MEXchange

면접 대비

시간 제한1초메모리 제한1024 MB

요약
순열 A의 접두 MEX 배열 B가 주어졌을 때, B를 만드는 순열 A를 구하거나 그런 순열이 없음을 판단합니다.
난이도

보통10점 중 5점

유형
그리디, 구현
정답자
아직 제출이 없습니다

문제

길이가 NN인 순열은 11부터 NN까지의 정수가 정확히 한 번씩 등장하는 수열이다. 예를 들어, [2,3,1,5,4]\left[ 2,3,1,5,4 \right]는 순열이지만, [1,2,2]\left[ 1,2,2 \right]는 22가 두 번 등장하므로 순열이 아니다. 또한 [1,3,4]\left[ 1,3,4 \right]는 길이가 33이지만 44를 포함하므로 순열이 아니다.

길이가 NN인 순열 AA가 주어졌을 때, 수열 BB를 다음과 같이 정의한다.

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)

길이가 NN인 수열 BB가 주어질 때, 순열 AA를 구하라.

MEX⁡(S)\operatorname{MEX}\left( S \right)는 집합 SS에 포함되지 않는 가장 작은 양의 정수이다. 예를 들어, MEX⁡({1,2,5})=3\operatorname{MEX}\left(\{ 1,2,5 \}\right) =3이고 MEX⁡({2,3,4})=1\operatorname{MEX}\left(\{ 2,3,4 \}\right) =1이다. 이 문제에서 정의한 MEX⁡\operatorname{MEX}는 그 값이 00이 될 수 없다는 점에 주의하라.

입력

첫째 줄에 순열 AA의 길이 NN이 주어진다. (3≤N≤200 000)\left( 3\leq N\leq 200\,000 \right)

둘째 줄에 수열 BB의 원소를 나타내는 NN개의 정수 BiB_i가 공백으로 구분되어 주어진다. (1≤Bi≤N+1)\left( 1\leq B_i\leq N+1 \right)

출력

첫째 줄에 BB가 되는 순열 AA가 존재하면 Yes를, 존재하지 않으면 No를 출력한다.

순열 AA가 존재하면 둘째 줄에 AA의 원소를 공백으로 구분하여 출력한다. 답이 여러 가지라면 아무거나 출력한다.

예제2

  1. 예제 1

    입력
    5
    1 2 2 2 6
    
    예상 출력
    Yes
    3 1 4 5 2
    
  2. 예제 2

    입력
    5
    1 4 4 4 6
    
    예상 출력
    No