Alice có một dãy số nguyên không âm \(a_1, a_2, \dots, a_n\) và định nghĩa một cách chia dãy \(k\) đoạn \((l_1, r_1), (l_2, r_2), \dots, (l_k, r_k)\) được gọi là cách chia \(x\)-đẹp thỏa mãn:

• Mỗi vị trí \(i\) (\(1 \le i \le n\)) thuộc đúng một đoạn. Cụ thể, tồn tại đúng một đoạn (\(l_t, r_t\)) mà \(l_t \le i \le r_t\).
• Số nguyên không âm nhỏ nhất không xuất hiện trong mỗi dãy con liên tiếp \(a_{l_t}, a_{l_t+1}, \dots, a_{r_t}\) không vượt quá \(x\).

Yêu cầu: Cho dãy số nguyên không âm \(n\) phần tử, hãy giúp Alice xác định mỗi giá trị \(x\) (\(0 \le x \le n-1\)) thì cách chia \(x\)-đẹp có số đoạn \(k\) nhỏ nhất là bao nhiêu?

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) (\(0 \le a_i \le 10^6\)).

Output

• Ghi ra \(n\) dòng tương ứng và kết quả cách chia \(x\)-đẹp với \(x\) từ \(0\) đến \(n-1\). Nếu không có cách chia thỏa mãn thì in ra -1.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 3000\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 2 \cdot 10^5\).
• Subtask \(4\) (\(20\%\) số điểm): \(k \le 20\) với mọi \(0 \le x \le n-1\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

5
2 0 1 0 3

-1
3
2
2
1