長さ $N$ の配列 $a$ が与えられる。$a$ の各要素は $-1$ であるか、$1$ から $N$ までの整数である。$1$ から $N$ までの各数は $a$ に高々一度しか現れない。また、$a$ の隣接する要素の差の絶対値は $1$ ではない。

以下の条件を満たす $\{1, 2, \dots, N\}$ の置換 $p$ のうち、辞書順最小のものを求めよ。

• $a_i \neq -1$ ならば、$a_i = p_i$ ($1 \leq i \leq N$)
• $|p_i - p_{i+1}| \neq 1$ ($1 \leq i \leq N - 1$)

入力

1行目に整数 $N$ が与えられる。 2行目にスペース区切りで $N$ 個の整数、すなわち配列 $a$ の要素が与えられる。

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

出力

条件を満たす置換 $p$ が存在しない場合は、$-1$ を出力せよ。 存在する場合は、辞書順最小の置換 $p$ を出力せよ。

入出力例

入力 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