시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)109423354.098%

문제

You are given an array $a$ of length $N$. Each element of $a$ is either -1 or an integer between $1$ and $N$. Each number between $1$ and $N$ appears at most once in $a$. Also, no two adjacent elements of $a$ have a difference of $1$.

You are to find the lexicographically smallest permutation $p$ of $\{1,2,\cdots ,N\}$ satisfying the following.

  • If $a_i\neq -1$, then $a_i=p_i$ ($1\leq i\leq N$)
  • $|p_i-p_{i+1}|\neq 1$ ($1\leq i\leq N-1$)

입력

The first line contains one integer, $N$.

The second line contains space-separated $N$ integers — elements of the array $a$.

출력

If there is no permutation $p$ satisfying the condition, then output a single integer $-1$.

Otherwise, output the lexicographically smallest permutation $p$.

제한

  • $1\leq N\leq 200,000$
  • $1\le a_i\le N$ or $a_i=-1$ ($1\leq i\leq N$)
  • $a_i\neq a_j$ or $a_i=-1$ ($1\leq i<j\leq N$)
  • $|a_i-a_{i+1}|\neq 1$ ($1\leq i\leq N-1$)

예제 입력 1

10
3 -1 10 -1 8 -1 -1 -1 -1 -1

예제 출력 1

3 1 10 2 8 4 6 9 5 7

예제 입력 2

2
-1 -1

예제 출력 2

-1