tornjevi — COCI CONTEST_#5
Task type: batch | Time limit: 2 s | Memory limit: 512 MB | Difficulty: 16
Algorithms: data structures, number theory, stack

# Task Tornjevi

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 \le i \le r$) is *good* in that subsequence if it holds that $h_i = \text{gcd}(h_l, h_{l+1}, \dots, h_r)$, where $\text{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.

## Input

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, \dots, h_n$ ($1 \le h_i \le 10^6$).

### Output

In a single line, print the answer to the above-mentioned question for each $i = 1, 2, \dots, n$, in order.

### Scoring

| Subtask | Points | Constraints |
|---|---|---|
| 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. |

#### Examples

| Input | Input |
|---|---|
| `6`<br>`3 6 6 6 1 3` | `5`<br>`10 2 10 15 5` |
| Output | Output |
| `4 3 3 3 6 1` | `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).

Starter code: