Trên một con phố nào đó, có \(n\) tòa tháp, được đánh số liên tiếp từ \(1\) đến \(n\). Mỗi tòa tháp có chiều cao riêng h_i, được biểu thị bằng mét.

Đối với một dãy con liên tiếp các tòa tháp được đánh số \(l, l + 1, ..., r\), ta nói rằng tòa tháp số \(i\) \((l \le i \le r)\) là tốt trong dãy con đó nếu thỏa mãn \(h_i = gcd(h_l, h_{l+1}, ..., h_r)\), trong đó \(gcd(a_1, a_2, ..., a_k)\) biểu thị ước chung lớn nhất của tập các số nguyên dương \(a_1, a_2, ..., a_k\).

Nhiệm vụ của bạn là xác định, với mỗi \(i = 1, 2, ..., n\), kích thước của dãy con liên tiếp lớn nhất mà trong đó tòa tháp số \(i\) là tốt, trong đó kích thước của một dãy con liên tiếp được định nghĩa là số lượng tòa tháp trong dãy con đó.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \le n \le 10^6)\), số lượng tòa tháp.
• Dòng thứ hai chứa n số nguyên, theo thứ tự, \(h_1, h_2, ..., h_n\) \((1 \le h_i \le 10^6)\).

Dữ liệu ra

• Trên một dòng duy nhất, in ra câu trả lời cho câu hỏi được đề cập ở trên cho mỗi \(i = 1, 2, ..., n\), theo thứ tự.

Chấm điểm

Input 1

6
3 6 6 6 1 3

Output 1

4 3 3 3 6 1

Input 2

5
10 2 10 15 5

Output 2

1 3 1 1 3

Giải thích ví dụ đầu tiên: Trong bốn tòa tháp đầu tiên, tòa tháp số 1 là tốt. Các tòa tháp số 2, 3 và 4 là tốt trong dãy con mà chúng tự tạo thành. Tòa tháp 5 sẽ là tốt trong bất kỳ dãy con tùy ý nào chứa nó, vì vậy câu trả lời sẽ là 6 (toàn bộ dãy).