H. Permutation Arrangement
time limit per test
1 s
memory limit per test
1024 mebibytes
input
standard input
output
standard output

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$$$ differ by exactly $$$1$$$.

You are to find the lexicographically smallest permutation $$$p$$$ of $$$\{1, 2, \ldots, 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$$$).
Input

The first line contains one integer, $$$N$$$.

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

  • $$$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 \lt j \leq N$$$)
  • $$$|a_i - a_{i + 1}| \neq 1$$$ ($$$1 \leq i \leq N - 1$$$)
Output

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

Otherwise, output the lexicographically smallest permutation $$$p$$$.

Examples
Input
10
3 -1 10 -1 8 -1 -1 -1 -1 -1
Output
3 1 10 2 8 4 6 9 5 7
Input
2
-1 -1
Output
-1