Giả sử ta có một chuỗi ngoặc đơn đúng, ta gọi chuỗi này là \(S\), khi đó \(S\) có hai cách giải mã sau đây:

• Cách 1: \(S\) sẽ được mã hóa dưới dạng \(P=p_1,p_2,...,p_n\). Trong đó \(p_i\) là số lượng ngoặc đơn trái "(" đứng trước ngoặc đơn phải ")" thứ \(i\) tính từ trái.

• Cách 2: \(S\) sẽ được mã hóa dưới dạng \(W=w_1,w_2,...,w_n\). Gọi \(r\) là vị trí dấu ngoặc đơn ")" thứ \(i\) tính từ trái sang. Gọi \(l\) là vị trí của dấu ngoặc đơn trái "(" tương thích với dấu ngoặc ")" đó. Khi đó \(w_i\) chính bằng số lượng dấu ngoặc đơn phải ")" nằm trong đoạn từ \(l\) tới \(r\).

• Ví dụ: Ta có chuỗi \(S=(((()()())))\). Khi đó ta có dãy \(P\) tương ứng là: \(P=4,5,6,6,6,6\) và dãy \(W\) tương ứng là \(W=1,1,1,4,5,6\). \(W[1] = 1\) vì dấu ngoặc đơn ")" thứ nhất nằm ở vị trí \(5\) tương ứng với dấu ngoặc "(" nằm ở vị trí \(4\). Trong đoạn \(4\) tới \(5\) của \(S\) có \(1\) dấu ngoặc đơn ")".

Yêu cầu: Cho dãy \(P\) bất kì, tìm dãy \(W\) tương ứng.

Input

• Dòng thứ nhất chứa chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\) - Là độ dài của dãy \(P\).

• Dòng thứ hai chứa \(n\) số nguyên dương \(p_i \ (1 \leq p_i \leq n)\) - Mỗi số cách nhau bởi dấu cách.

Output

• Nếu không tồn tại dãy \(W\) thỏa mãn yêu cầu bài toán, in ra \(-1\). Ngược lại, in ra dãy \(W\) cần tìm.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n\leq 10\)..
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 100\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 5000\).
• Subtask \(4\) (\(40\%\) số điểm): \(n \leq 10^5\).

Example

3
2 2 3 

1 2 1