给定一个长度为 $N$ 的数组 $a$。$a$ 中的每个元素要么是 $-1$，要么是 $1$ 到 $N$ 之间的整数。$1$ 到 $N$ 之间的每个数字在 $a$ 中最多出现一次。此外，$a$ 中没有两个相邻元素的差的绝对值为 $1$。

你需要找到字典序最小的排列 $p$（由 $\{1, 2, \dots, N\}$ 组成），满足以下条件：

• 如果 $a_i \neq -1$，则 $a_i = p_i$ ($1 \le i \le N$)；
• $|p_i - p_{i+1}| \neq 1$ ($1 \le i \le N - 1$)。

输入格式

第一行包含一个整数 $N$。 第二行包含 $N$ 个空格分隔的整数：数组 $a$ 的元素。

• $1 \le N \le 200\,000$
• $1 \le a_i \le N$ 或 $a_i = -1$ ($1 \le i \le N$)
• $a_i \neq a_j$ 或 $a_i = -1$ ($1 \le i < j \le N$)
• $|a_i - a_{i+1}| \neq 1$ ($1 \le i \le 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