某条街道上有 $n$ 座塔楼，编号依次为 $1$ 到 $n$。每座塔楼的高度为 $h_i$（以米为单位）。 对于编号为 $l, l+1, \ldots, r$ 的**连续子序列**，若编号为 $i$（$l \leq i \leq r$）的塔楼满足 $h_i = \gcd(h_l, h_{l+1}, \ldots, h_r)$，则称该塔在此子序列中是$\tt{good}$的。其中 $\tt{\gcd}$ 表示一组正整数的最大公约数。 请为每个 $i = 1, 2, \ldots, n$，找出包含该塔的最长**连续子序列**的长度（子序列长度定义为包含的塔数）。

第一行包含整数 $n$（$1 \leq n \leq 10^6$），表示塔的数量。 第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$（$1 \leq h_i \leq 10^6$）。

在一行中按顺序输出每个 $i$ 对应的答案。

- 第一个样例解释：前四座塔的连续子序列中，编号 $1$ 的塔是$\tt{good}$的。编号 $2$、$3$、$4$ 的塔在它们组成的子序列中是$\tt{good}$的。编号 $5$ 的塔在所有包含它的子序列中都是$\tt{good}$的，因此答案为 $6$（整个序列长度）