Permutation Construction

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

요약

각 위치 i마다 오른쪽에서 P_i보다 큰 값이 처음 나타나는 위치(없으면 -1)가 주어질 때, 이를 만족하는 1부터 N까지의 순열을 만들거나 불가능하면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 스택, 그리디, 배열, 구현
정답자: 아직 제출이 없습니다

문제

Adrian challenges you to construct a permutation of $1$ to $N$ (inclusive) that satisfies his requirements. Suppose that your permutation is denoted as $P$ . There are $N$ requirements, numbered from $1$ to $N$ . Requirement $i$ is represented by $A\_i$ , which can be one of the followings:

if $A\_i = -1$ , then there is no $x$ that satisfy $x > i$ and $P\_x > P\_i$ ; or
if $i < A\_i ≤ N$ , then $A\_i$ is the smallest index larger than $i$ that satisfy $P\_{A\_i} > P\_i$ .

Construct any permutation that satisfies all of the requirements, or tell Adrian if it is impossible to construct such a permutation.

Note that a permutation of $1$ to $N$ (inclusive) is a sequence where each integer from $1$ to $N$ appears in the sequence exactly once.

입력

Input begins with an integer $N$ ( $1 ≤ N ≤ 100\\, 000$ ). The next line contains $N$ integers $A\_i$ ( $A\_i = -1$ or $i < A\_i ≤ N$ ) representing the given requirements.

출력

If at least one permutation that satisfies all the requirements can be found, output $N$ space-separated integers in a single line representing the permutation. If there are several permutations that satisfy all of the requirements, output any of them.

If there is no permutation that satisfies all the requirements, output -1 in a single line.

예제2

예제 1
입력
```
5
4 3 4 -1 -1
```
예상 출력
```
4 1 3 5 2
```
예제 2
입력
```
5
-1 -1 5 -1 -1
```
예상 출력
```
-1
```