아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

MEXchange

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

요약
접두사 MEX 수열 B가 주어질 때, 이를 만드는 순열 A가 존재하는지 판정하고 하나를 복원한다.
난이도

보통10점 중 5점

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

문제

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

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

B_i=MEX⁡(A_1,A_2,⋯ ,A_i) (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개의 정수 B_iB\_i가 공백으로 구분되어 주어진다. (1≤B_i≤N+1)\left( 1\leq B\_i\leq N+1 \right)

출력

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

만약 존재한다면 둘째 줄에 순열 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