P11753 [COCI 2024/2025 #5] 塔楼 / Tornjevi
题目背景
译自 [COCI 2024/2025 #5](https://hsin.hr/coci/) 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)$。
输入格式
无
输出格式
无
说明/提示
#### 数据范围
对于 $100\%$ 的数据，保证 $1\le n,h_i\le 10^6$。
| 子任务编号 | $n\le$ | 特殊性质 | 得分 |
| :--: | :--: | :--: | :--: |
| $ 1 $ | $100$ | | $ 7 $ |
| $ 2 $ | $5\times 10^3$ | | $ 11 $ |
| $ 3 $ | $5\times 10^4$ | | $ 17 $ |
| $ 4 $ | $10^6$ | A | $ 29 $ |
| $ 5 $ | $10^6$ | | $26$ |
特殊性质 A：$h_i\le 100$。