题目背景

译自 COCI 2024/2025 #5 T3。$\texttt{2s,0.5G}$。满分为 $90$。

题目描述

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

对于区间 $[l,r]$，我们称 $i$（$l\le i\le r$）关于 $[l,r]$ 是好的，当且仅当：$h_i=\gcd(h_l,h_{l+1},\ldots,h_r)$。

对于 $i$，定义 $f(i)$ 表示：所有 $i$ 关于 $[l,r]$ 是好的区间中，$r-l+1$ 的最大值。

对于 $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$。