该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一条街道上，有$n$座塔，从$1$到$n$连续编号。每座塔都有自己的高度$h_i$，以米为单位。

对于编号为$l,l+1,\dots,r$的连续塔子序列，如果塔$i$（满足$l \leq i \leq r$）满足$h_i = \gcd(h_l,h_{l+1},\dots,h_r)$，则称塔$i$在该子序列中是_好_的。其中，$\gcd(a_1,a_2,\dots,a_k)$表示正整数集合$a_1,a_2,\dots,a_k$的最大公约数。

你的任务是确定，对于每个$i=1,2,\dots,n$，包含塔$i$的最大连续子序列的长度（在该子序列中塔$i$是_好_的）。连续子序列的长度定义为该子序列中塔的数量。

输入格式

第一行包含一个整数$n$（$1 \leq n \leq 10^6$），表示塔的数量。

第二行包含$n$个整数，依次为$h_1,h_2,\dots,h_n$（$1 \leq h_i \leq 10^6$）。

输出格式

输出在一行中，按顺序输出每个$i=1,2,\dots,n$的答案。

数据范围

对于$100\%$的数据，保证$1 \leq n,h_i \leq 10^6$。

样例数据

6
3 6 6 6 1 3

4 3 3 3 6 1

说明

• 塔$1$在子序列$[1,4]$（长度为$4$）中是好的。
• 塔$2$,$3$,$4$在各自长度为$3$的子序列（如$[2,4]$）中是好的。
• 塔$5$在任意包含它的子序列中都是好的，因此整个序列（长度为$6$）满足条件。
• 塔$6$仅能在子序列$[6,6]$（长度为$1$）中满足条件。

5
10 2 10 15 5

1 3 1 1 3