길이가 $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 \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