On vous donne un tableau $a$ de longueur $N$. Chaque élément de $a$ est soit $-1$, soit un entier compris entre $1$ et $N$. Chaque nombre entre $1$ et $N$ apparaît au plus une fois dans $a$. De plus, aucun élément adjacent de $a$ ne diffère exactement de $1$.

Vous devez trouver la permutation $p$ de $\{1, 2, \dots, N\}$ lexicographiquement la plus petite satisfaisant les conditions suivantes :

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

Entrée

La première ligne contient un entier, $N$. La deuxième ligne contient $N$ entiers séparés par des espaces : les éléments du tableau $a$.

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

Sortie

S'il n'existe aucune permutation $p$ satisfaisant la condition, affichez un seul entier $-1$. Sinon, affichez la permutation $p$ lexicographiquement la plus petite.

Exemples

Entrée 1

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

Sortie 1

3 1 10 2 8 4 6 9 5 7

Entrée 2

2
-1 -1

Sortie 2

-1