시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB54224318049.587%

문제

코치 희승이는 FXC 나라 육상 국가대표 선발 보고서를 작성하였다. 희승이는 보고서를 작성할 때 목차를 육상협회에서 사용하는 글머리 기호 형태로 작성하였다. 희승이가 FXC 나라 문화체육관광부로 공문을 보내려고 봤더니, 문화체육관광부에서는 공문을 작성할 때 글머리 번호 형태로 작성한다. 따라서 희승이는 보고서를 글머리 번호 형태로 바꾼 사본을 만들어서 문화체육관광부로 보내려고 한다.

보고서 목차는 위 그림의 트리와 같이 도식화할 수 있다. 트리에서 루트를 제외한 모든 노드는 보고서의 항목과 일대일 대응된다. 트리에서 깊이 우선 탐색(DFS)을 했을 때 방문하는 순서대로 트리 노드에 색인을 매길 수 있는데, 보고서에서 먼저 등장하는 항목이 더 작은 색인을 가진다. 보고서를 글머리 기호 형태로 작성한다면 각 항목의 번호는 항목과 대응하는 노드의 레벨(루트 노드와의 거리)과 같다. 한편 보고서를 글머리 번호 형태로 작성한다면 각 항목의 번호는 항목과 대응하는 노드보다 색인이 작은 형제 노드의 수에 $1$을 더한 값과 같다.

희승이가 글머리 기호 형태로 작성한 보고서 목차가 주어지면 이를 글머리 번호 형태로 변환하는 프로그램을 작성하여라.

입력

첫 번째 줄에 보고서 목차 내 항목의 개수 $C$가 주어진다.

두 번째 줄에는 글머리 기호 형태로 작성된 보고서에서 $i+1$번째($0 \leq i < C$) 항목의 번호 $M_i$에 해당하는 $C$개의 정수가 주어진다.

출력

만약 주어진 보고서가 올바른 보고서가 아닌 경우 첫 번째 줄에 -1을 출력한다. 보고서가 올바르다면 항목의 번호가 입력과 동일하게 매겨지도록 보고서와 대응되는 트리를 만들 수 있다.

주어진 보고서가 올바른 보고서라면 첫 번째 줄에 $C$개의 정수 $N_i$를 출력한다. $N_i$는 주어진 보고서를 글머리 번호 형태로 바꿨을 때 $i+1$번째($0 \leq i < C$) 항목의 번호를 의미한다.

가능한 정답이 여러 가지라면 그중 아무거나 출력한다.

서브태스크

모든 데이터에 대해서, $1 ≤ C ≤ 10^6$; $1 ≤ M_i ≤ 10^6$을 만족한다.

번호배점제한
11

문제에서 주어진 예제만 들어온다.

21

$M_i ≤ 2$

31

추가 제약조건은 없다.

예제 입력 1

10
1 2 2 2 1 2 3 3 2 2

예제 출력 1

1 1 2 3 2 1 1 2 2 3

예제 입력 2

7
1 2 3 4 3 2 1

예제 출력 2

1 1 1 1 2 2 2

예제 입력 3

5
1 3 5 7 9

예제 출력 3

-1

출처

Contest > BOJ User Contest > FunctionCup > FunctionCup 2023 MN번

채점 및 기타 정보

  • 예제는 채점하지 않는다.