Se te da un arreglo $a$ de longitud $N$. Cada elemento de $a$ es $-1$ o un número entero entre $1$ y $N$. Cada número entre $1$ y $N$ aparece a lo sumo una vez en $a$. Además, no hay dos elementos adyacentes en $a$ que difieran exactamente en $1$.

Debes encontrar la permutación lexicográficamente más pequeña $p$ de $\{1, 2, \dots, N\}$ que satisfaga lo siguiente:

• si $a_i \neq -1$, entonces $a_i = p_i$ ($1 \leq i \leq N$);
• $|p_i - p_{i+1}| \neq 1$ ($1 \leq i \leq N - 1$).

Entrada

La primera línea contiene un número entero, $N$. La segunda línea contiene $N$ números enteros separados por espacios: los elementos del arreglo $a$.

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

Salida

Si no existe una permutación $p$ que satisfaga la condición, imprime un único número entero $-1$. De lo contrario, imprime la permutación $p$ lexicográficamente más pequeña.

Ejemplos

Entrada 1

10
3 -1 10 -1 8 -1 -1 -1 -1 -1

Salida 1

3 1 10 2 8 4 6 9 5 7

Entrada 2

2
-1 -1

Salida 2

-1