시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 127 41 35 41.176%

문제

이진 트리란 각각의 노드가 0, 1, 2개의 자식 노드를 가지는 트리 자료 구조이다.

이진 탐색 트리란 각 노드의 왼쪽 서브트리(subtree)는 그 노드의 값보다 작은 노드 값들로, 오른쪽 서브트리(subtree)는 그 노드의 값보다 큰 노드 값들로 이루어져 있는 이진 트리를 말한다.

아래의 그림은 1부터 9까지의 수를 값으로 지닌 노드로 이루어져 있는 이진 탐색 트리의 예시이다.

또한, 이진 탐색 트리에 새로운 노드를 삽입하는 과정은 다음과 같다.

루트 노드부터 탐색하여 Insert 하는 값이 현재 노드의 값보다 크면 오른쪽 자식 노드를 방문, 작으면 왼쪽 자식 노드을 방문하는 것을 반복하다가 비어있는 자리에 해당하는 값을 가진 노드를 삽입한다.

아래는 값이 4인 노드를 루트로 하는 트리에 [2, 3, 5, 1]를 순차적으로 삽입하는 예시이다.

1부터 N까지의 모든 정수를 한 번씩 포함하고 있는 수열 A1, A2, ..., AN이 있다.

값이 A1인 노드를 루트로 하는 트리에 A2, A3, ..., A을 순서대로 삽입하려 한다.

N-1개의 노드를 삽입할 때마다 루트에서 그 노드에 도달하기 위해 거쳐야 하는 간선의 수, 즉 노드의 깊이가 주어질 때 A1, A2, ..., AN을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 N이 주어진다. (2 ≤ N ≤ 300,000)

둘째 줄에는 A2부터 AN을 순서대로 삽입할 때마다 삽입된 노드의 깊이가 공백으로 구분하여 주어진다.

이때 노드의 깊이는 1이상 N미만의 자연수이다.

출력

가능한 수열이 있다면 첫째 줄에 수열 A1, A2, ..., AN의 값을 공백으로 구분하여 출력한다.

가능한 수열이 여러 개라면 아무거나 출력해도 좋다.

가능한 수열이 없다면 첫째 줄에 -1을 출력한다.

예제 입력 1

5
1 2 1 2

예제 출력 1

4 2 3 5 1

예제 입력 2

9
1 2 2 1 3 2 3 3

예제 출력 2

5 3 1 4 9 2 7 8 6

예제 입력 3

5
4 3 2 1

예제 출력 3

-1