시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 1024 MB171928655.484%

문제

아케인리버에 서식하는 돌의 정령은 무리를 지어 활동하는 경향이 있다. 이때, 어느 돌의 정령 무리의 키는 돌의 정령들이 쌓인 구조의 층수라고 한다.

키가 3인 돌의 정령 무리이다.

키가 7인 돌의 정령 무리이다.

오른쪽을 바라보고 있는 $1$부터 $N$까지의 서로 다른 키를 가진 $N$개의 돌의 정령 무리가 있다. 이때, 돌의 정령들은 자신이 속한 무리보다 키가 큰 돌의 정령 무리 너머를 볼 수 없다. 만약 $i$번째 위치에 있는 돌의 정령이 $j$번째 돌의 정령 무리까지 볼 수 있다면, $i$번째 무리의 '시야 점수'는 $j-i$로 정의한다. 만약 앞에 자신보다 키가 큰 무리가 존재하지 않는다면 시야 점수는 $10^9$으로 정의한다. 

아케인리버를 탐험하고 있는 여러분은 크기 $N$의 배열 $A$를 받아, 만약 $A_i$가 음수라면, $i$번째 위치의 무리의 시야점수는 $-A_i$ 이하이고, $A_i$가 양수라면 $i$번째 무리의 시야점수는 $A_i$ 이상이도록 돌의 정령 무리를 배치하라는 퀘스트를 받았다.

퀘스트를 완료할 수 있도록 돌의 정령 무리를 배치해보자. 만약 가능한 경우가 여러 개 있다면 어떤 방법을 선택해도 좋다.

입력

첫째 줄에 돌의 정령 무리의 수 $N$이 주어진다. ($1 \leq N \leq 70,000$)

둘째 줄에 시야점수의 제한을 나타내는 크기 $N$의 배열 $A$가 주어진다. ($-N \leq A_i \leq N$, $A_i \neq 0$)

출력

조건을 만족하는 배치가 있다면, 돌의 정령 무리들의 키를 나타내는 배열을 한 줄에 출력한다. 배열의 $i$번째 수는 왼쪽에서 $i$번째에 놓인 돌의 정령 무리의 키와 같아야 한다. 조건을 만족하는 배치가 여러 개라면, 아무 배치나 출력하여라. 조건을 만족하는 배치가 없다면 -1을 출력한다.

예제 입력 1

5
2 -2 4 1 2

예제 출력 1

4 1 5 2 3

$4$, $1$, $5$, $2$, $3$으로 배치한다면 돌의 정령 무리들의 시야점수는 각각 $2$, $1$, $10^9$, $1$, $10^9$로 조건을 만족한다.

예제 입력 2

7
2 3 -1 2 4 5 -1

예제 출력 2

-1

가장 오른쪽 돌의 정령 무리의 시야점수를 1 이하로 만들 수 없기 때문에 -1을 출력한다.

출처

High School > 경기과학고등학교 > 나는코더다 2021 송년대회 C번