#P11753. [COCI 2024/2025 #5] 塔楼 / Tornjevi

[COCI 2024/2025 #5] 塔楼 / Tornjevi

题目背景

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

题目描述

给定正整数序列 h1,,hnh_1,\ldots,h_n

对于区间 [l,r][l,r],我们称 iilirl\le i\le r)关于 [l,r][l,r]好的,当且仅当:hi=gcd(hl,hl+1,,hr)h_i=\gcd(h_l,h_{l+1},\ldots,h_r)

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

对于 i=1,2,,ni=1,2,\ldots,n,求出 f(i)f(i)

输入格式

第一行,正整数 nn

第二行,nn 个正整数 h1,h2,,hnh_1,h_2,\ldots,h_n

输出格式

输出 nn 个正整数 f(1),f(2),,f(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%100\% 的数据,保证 1n,hi1061\le n,h_i\le 10^6

子任务编号 nn\le 特殊性质 得分
1 1 100100 7 7
2 2 5×1035\times 10^3 11 11
3 3 5×1045\times 10^4 17 17
4 4 10610^6 A 29 29
5 5 2626

特殊性质 A:hi100h_i\le 100