Permutation Arrangement

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$)