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

译自 [COCI 2024/2025 #5](https://hsin.hr/coci/) T3。$\texttt{2s,0.5G}$。满分为 $90$。

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, \ldots, 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}, \ldots , h_r)$, where $\gcd (a_1, a_2, \ldots , a_k)$ denotes the greatest common divisor of the set of positive integers $a_1, a_2, \ldots , a_k$. Your task is to determine, for each $i = 1, 2, \ldots , 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.

N/A

N/A

**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). ### Scoring | Subtask | Points | Constraints | | :-: | :-: | :-: | | $1$ | $7 $ |$n ≤ 100 $| | $2$ | $11$ |$ n ≤ 5000 $| | $3$ | $17$ |$ n ≤ 50000 $| | $4$ | $29$ |$ h_i ≤ 100 $| | $5$ | $26$ |No additional constraints. |