← 返回题目列表

Codeforces · 1632/D

D. 新年音乐会

中文机器翻译题面 查看原题

新年即将来临,这意味着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$$$。

为了避免让观众感到无聊,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 \cdot 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

1
1

输出 #1

1

输入 #2

3
1 4 2

输出 #2

1 1 2

输入 #3

7
2 12 4 8 18 3 6

输出 #3

0 1 1 1 2 2 2

注意

在第一个测试中,我们可以将 $$$1$$$ 更改为 $$$2$$$,所以答案是 $$$1$$$。

在第二次测试中:

- $$$[1]$$$ 可以改为 $$$[2]$$$,
- $$$[1, 4]$$$ 可以改为 $$$[3, 4]$$$,
- $$$[1, 4, 2]$$$ 可以更改为 $$$[2, 3, 2]$$$。