Дан массив $a$ длины $N$. Каждый элемент $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