CF1632D.New Year Concert

New Year is just around the corner, which means that in School 179, preparations for the concert are in full swing.

There are $n$ classes in the school, numbered from $1$ to $n$, the $i$-th class has prepared a scene of length $a_i$ minutes.

As the main one responsible for holding the concert, Idnar knows that if a concert has $k$ scenes of lengths $b_1$, $b_2$, $\ldots$, $b_k$ minutes, then the audience will get bored if there exist two integers $l$ and $r$ such that $1 \le l \le r \le k$ and $\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r) = r - l + 1$, where $\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r)$ is equal to the greatest common divisor (GCD) of the numbers $b_l$, $b_{l + 1}$, $\ldots$, $b_{r - 1}$, $b_r$.

To avoid boring the audience, Idnar can ask any number of times (possibly zero) for the $t$-th class ($1 \le t \le k$) to make a new scene $d$ minutes in length, where $d$ can be any positive integer. Thus, after this operation, $b_t$ is equal to $d$. Note that $t$ and $d$ can be different for each operation.

For a sequence of scene lengths $b_1$, $b_2$, $\ldots$, $b_{k}$, let $f(b)$ be the minimum number of classes Idnar has to ask to change their scene if he wants to avoid boring the audience.

Idnar hasn't decided which scenes will be allowed for the concert, so he wants to know the value of $f$ for each non-empty prefix of $a$. In other words, Idnar wants to know the values of $f(a_1)$, $f(a_1$,$a_2)$, $\ldots$, $f(a_1$,$a_2$,$\ldots$,$a_n)$.

新年即将来临，这意味着学校179的音乐会筹备工作正在如火如荼地进行。

学校共有 $n$ 个班级，编号从 $1$ 到 $n$，其中第 $i$ 个班级准备了一个时长为 $a_i$ 分钟的节目。

作为音乐会的主要负责人，Idnar 知道：若一场音乐会包含 $k$ 个节目，其时长分别为 $b_1, b_2, \ldots, b_k$ 分钟，则当存在两个整数 $l$ 和 $r$ 满足 $1 \le l \le r \le k$，且 $\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r) = r - l + 1$ 时，观众将感到乏味。此处 $\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r)$ 表示数列 $b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r$ 的最大公约数（GCD）。

为避免观众感到乏味，Idnar 可以任意次数（包括零次）地要求第 $t$ 个班级（$1 \le t \le k$）重新制作一个时长为 $d$ 分钟的新节目，其中 $d$ 可为任意正整数；执行该操作后，$b_t$ 即被替换为 $d$。注意：每次操作中 $t$ 和 $d$ 均可不同。

对于节目时长序列 $b_1, b_2, \ldots, b_k$，记 $f(b)$ 为 Idnar 为避免观众乏味而需请求更改节目的最少班级数量。

Idnar 尚未确定哪些节目将被允许登上音乐会舞台，因此他希望知道 $f$ 在 $a$ 的每个非空前缀上的取值。换言之，Idnar 希望获知以下各值：$f(a_1)$、$f(a_1,a_2)$、$\ldots$、$f(a_1,a_2,\ldots,a_n)$。

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of classes in the school.

The second line contains $n$ positive integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \le a_i \le 10^9$) — the lengths of the class scenes.

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示学校中班级的数量。

第二行包含 $n$ 个正整数 $a_1$, $a_2$, $\ldots$, $a_n$（$1 \le a_i \le 10^9$）—— 表示各班级场景的长度。

Print a sequence of $n$ integers in a single line — $f(a_1)$, $f(a_1$,$a_2)$, $\ldots$, $f(a_1$,$a_2$,$\ldots$,$a_n)$.

在一行中输出 $n$ 个整数的序列：$f(a_1)$、$f(a_1,a_2)$、$\ldots$、$f(a_1,a_2,\ldots,a_n)$。

In the first test we can change $1$ to $2$, so the answer is $1$.

In the second test:

• $[1]$ can be changed into $[2]$,
• $[1, 4]$ can be changed into $[3, 4]$,
• $[1, 4, 2]$ can be changed into $[2, 3, 2]$.

在第一个测试用例中，我们可以将 $1$ 改为 $2$，因此答案是 $1$。

在第二个测试用例中：

• $[1]$ 可以改为 $[2]$，
• $[1, 4]$ 可以改为 $[3, 4]$，
• $[1, 4, 2]$ 可以改为 $[2, 3, 2]$。