Good Indices Interval

Given a sequence of positive integers (h_1, h_2, \ldots, h_n). For a subarray ([l, r]), an index (i) with (l \le i \le r) is said to be good with respect to ([l, r]) if and only if [ h_i = \gcd(h_l, h_{l+1}, \ldots, h_r), ] where the (\gcd) is computed in the usual way. For each index (i), define (f(i)) as the maximum length (r-l+1) among all subarrays ([l, r]) for which index (i) is good. Compute (f(i)) for every (i = 1, 2, \ldots, n).

inputFormat

The first line contains a single integer (n) (e.g. (1 \le n \le 10^5)). The second line contains (n) positive integers (h_1, h_2, \ldots, h_n) separated by spaces.

outputFormat

Print (n) integers (f(1), f(2), \ldots, f(n)) separated by spaces, where (f(i)) is the maximum length of a subarray ([l, r]) for which index (i) is good.

sample

5
2 4 8 3 9

3 2 1 2 1