Bạn được cho một mảng $a$ có độ dài $N$. Mỗi phần tử của $a$ là $-1$ hoặc một số nguyên từ $1$ đến $N$. Mỗi số từ $1$ đến $N$ xuất hiện tối đa một lần trong $a$. Ngoài ra, không có hai phần tử liền kề nào của $a$ có hiệu bằng đúng $1$.

Bạn cần tìm hoán vị $p$ của $\{1, 2, \dots, N\}$ nhỏ nhất theo thứ tự từ điển thỏa mãn các điều kiện sau:

• Nếu $a_i \neq -1$, thì $a_i = p_i$ ($1 \le i \le N$);
• $|p_i - p_{i+1}| \neq 1$ ($1 \le i \le N - 1$).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$. Dòng thứ hai chứa $N$ số nguyên cách nhau bởi dấu cách: các phần tử của mảng $a$.

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

Dữ liệu ra

Nếu không tồn tại hoán vị $p$ thỏa mãn điều kiện, hãy in ra một số nguyên $-1$. Nếu tồn tại, hãy in ra hoán vị $p$ nhỏ nhất theo thứ tự từ điển.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3 1 10 2 8 4 6 9 5 7

Dữ liệu vào 2

2
-1 -1

Dữ liệu ra 2

-1