Description

On a certain street, there are $n$ towers, numbered consecutively from $1$ to $n$. Each tower has its own height $h_i$, expressed in meters.

For a consecutive subsequence of towers numbered $l, l + 1, \ldots, r$, we say that the tower with number $i$ ($l ≤ i ≤ r$) is good in that subsequence if it holds that $h_i = \gcd (h_l, h_{l+1}, \ldots , h_r)$, where $\gcd (a_1, a_2, \ldots , a_k)$ denotes the greatest common divisor of the set of positive integers $a_1, a_2, \ldots , a_k$.

Your task is to determine, for each $i = 1, 2, \ldots , n$, the size of the largest consecutive subsequence in which the tower with number $i$ is good, where the size of a consecutive subsequence is defined as the number of towers in that subsequence.

Input Format

In the first line, there is an integer $n$ ($1 ≤ n ≤ 10^6$), the number of towers.

In the second line, there are $n$ integers, in order, $h_1, h_2, \ldots, h_n$ ($1 ≤ h_i ≤ 10^6$).

Output Format

In a single line, print the answer to the above-mentioned question for each $i = 1, 2, \ldots , n$, in order.

6
3 6 6 6 1 3

4 3 3 3 6 1

5
10 2 10 15 5

1 3 1 1 3

Hint

Clarification of the first example:

In the first four towers, tower number $1$ is good. Towers with numbers $2, 3$, and $4$ are good in the subsequence they form themselves. Tower $5$ will be good in any arbitrary subsequence that contains it, so the answer will be 6 (the entire sequence).

Scoring