题目描述

给定正整数序列 $h_1,\ldots,h_n$。

对于区间 $[l,r]$，如果 $h_i$ 满足 $l\le i\le r$，且 $h_i=\gcd(h_l,h_{l+1},\ldots,h_r)$，我们就认为 $i$ 关于区间 $[l,r]$ 是匹配的。

定义 $f(i)$ 表示：所有 $i$ 关于 $[l,r]$ 是匹配的区间中，$r-l+1$ 的最大值。简单来说就是 $h_i$ 最多能匹配上多长的区间。

对于 $i=1,2,\ldots,n$，求出 $f(i)$。

输入格式

第一行，正整数 $n$。

第二行，$n$ 个正整数 $h_1,h_2,\ldots,h_n$。

输出格式

输出 $n$ 个正整数 $f(1),f(2),\ldots,f(n)$。

6
3 6 6 6 1 3

4 3 3 3 6 1

5
10 2 10 15 5

1 3 1 1 3

提示

数据范围

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

特殊性质 A：$h_i\le 100$。