레이팅 미적용On a certain street, there are \(n\) towers, numbered consecutively from 1 to \(n\). Each
tower has its own height \(h_{i}\), expressed in meters.
For a consecutive subsequence of towers numbered \(l\), \(l + 1\), . . ., \(r\), we say that
the tower with number \(i\) (\(l \le i \le r\)) is good in that subsequence if it holds that
\(h_{i} = gc\)d (\(h_{l}\), h_{\(l+1\)}, . . . , \(h_{r}\)), where gcd (\(a_{1}\), \(a_{2}\), . . . , \(a_{k}\)) denotes the greatest common
divisor of the set of positive integers \(a_{1}\), \(a_{2}\), . . . , \(a_{k}\).
Your task is to determine, for each \(i = 1\), 2, . . . , n, the size of the largest consecutive
subsequence in which the tower with number \(i\) is good, where the size of a consecutive subsequence is
defined as the number of towers in that subsequence.
In the first line, there is an integer \(n\) (\(1 \le n \le 10^{6}\)), the number of towers.
In the second line, there are \(n\) integers, in order, \(h_{1}\), \(h_{2}\), . . ., \(h_{n}\) (\(1 \le h_{i} \le 10^{6}\)).
In a single line, print the answer to the above-mentioned question for each \(i = 1\), 2, . . . , n, in order.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 7점 | \(n \le 100\) |
2 | 11점 | \(n \le 5000\) |
3 | 17점 | \(n \le 50000\) |
4 | 29점 | \(h_{i} \le 100\) |
5 | 26점 | No additional constraints. |
6
3 6 6 6 1 34 3 3 3 6 15
10 2 10 15 51 3 1 1 3Clarification of the first example: In the first four towers, tower number 1 is good. Towers with
numbers 2, 3, and 4 are good in the subsequence they form themselves. Tower 5 will be good in any
arbitrary subsequence that contains it, so the answer will be 6 (the entire sequence).