在一条街道上，有 $n$ 座塔，编号依次为 $1$ 到 $n$。每座塔都有其高度 $h_i$（单位为米）。
对于一个编号为 $l, l+1, \dots, r$ 的连续塔子序列，如果满足 $h_i = \gcd(h_l, h_{l+1}, \dots, h_r)$，则称编号为 $i$ ($l \le i \le r$) 的塔在该子序列中是“好的”，其中 $\gcd(a_1, a_2, \dots, a_k)$ 表示正整数集合 $a_1, a_2, \dots, a_k$ 的最大公约数。
你的任务是对于每个 $i = 1, 2, \dots, n$，确定编号为 $i$ 的塔在其中是“好的”的最长连续子序列的长度，其中连续子序列的长度定义为该子序列中塔的数量。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示塔的数量。
第二行包含 $n$ 个整数，依次为 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^6$)。
输出格式
在一行中，按顺序输出每个 $i = 1, 2, \dots, n$ 对应的答案。
评分
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 7 | $n \le 100$ |
| 2 | 11 | $n \le 5000$ |
| 3 | 17 | $n \le 50000$ |
| 4 | 29 | $h_i \le 100$ |
| 5 | 26 | 无额外限制 |
样例
输入格式 1
6 3 6 6 6 1 3
输出格式 1
4 3 3 3 6 1
说明
第一个样例的解释：在前四座塔中，1 号塔是好的。编号为 2、3 和 4 的塔在它们自身组成的子序列中是好的。5 号塔在任何包含它的子序列中都是好的，因此答案是 6（整个序列）。
输入格式 2
5 10 2 10 15 5
输出格式 2
1 3 1 1 3