CF1632D New Year Concert

新年即将到来，这意味着 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) = r - l + 1$，观众就会感到无聊。其中 $\gcd(b_l, b_{l+1}, \ldots, b_r)$ 表示这些数的最大公约数。 为了避免观众感到无聊，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 还没有决定哪些节目会被选入音乐会，因此他想知道对于 $a$ 的每一个非空前缀，$f$ 的值分别是多少。换句话说，Idnar 想知道 $f(a_1), f(a_1, a_2), \ldots, f(a_1, a_2, \ldots, a_n)$ 的值。

第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）——学校的班级数。 第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——各班级准备的节目时长。

输出一行 $n$ 个整数，依次表示 $f(a_1), f(a_1, a_2), \ldots, f(a_1, a_2, \ldots, a_n)$。

在第一个测试中，可以将 $1$ 改为 $2$，所以答案是 $1$。 在第二个测试中： - $[1]$ 可以改为 $[2]$， - $[1, 4]$ 可以改为 $[3, 4]$， - $[1, 4, 2]$ 可以改为 $[2, 3, 2]$。 由 ChatGPT 4.1 翻译