| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 3 | 3 | 3 | 100.000% |
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, \dots , r$, we say that the tower with number $i$ ($l ≤ i ≤ r$) is good in that subsequence if it holds that $h_i = \gcd (h_l , h_{l+1}, \dots , h_r)$, where $\gcd (a_1, a_2, \dots , a_k)$ denotes the greatest common divisor of the set of positive integers $a_1, a_2, \dots , a_k$.
Your task is to determine, for each $i = 1, 2, \dots , 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 ≤ n ≤ 10^6$), the number of towers.
In the second line, there are $n$ integers, in order, $h_1, h_2, \dots , h_n$ ($1 ≤ h_i ≤ 10^6$).
In a single line, print the answer to the above-mentioned question for each $i = 1, 2, \dots , n$, in order.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $n ≤ 100$ |
| 2 | 11 | $n ≤ 5000$ |
| 3 | 17 | $n ≤ 50000$ |
| 4 | 29 | $h_i ≤ 100$ |
| 5 | 26 | No additional constraints. |
6 3 6 6 6 1 3
4 3 3 3 6 1
5 10 2 10 15 5
1 3 1 1 3
Clarification 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).