题目描述

哥萨克 Vus 得到了一个包含 $n$ 个整数的数组 $a$。随后，他被告知存在另一个同样由 $n$ 个整数组成的数组 $b$，但具体内容未知。为了确定数组 $b$，哥萨克可以无限次使用以下操作

• 选择两个整数 $1 \leq l \leq r \leq n$。
• 查询 $b_l + b_{l + 1} + \dots + b_r$ 的和。
• 支付 $\gcd(a_l, a_{l+1}, ..., a_r)$ 戈比，其中 $\gcd$ 表示最大公约数（例如 $\gcd(3, 5) = 1$，而 $\gcd(15, 30, 6) = 3$）。

Vus 需要你求出确定数组 $b$ 所需的最小戈比数。

随后，哥萨克会对数组 $a$ 进行 $q$ 次修改，每次将某个 $a_i$ 改为 $x$。每次修改后，你需要重新计算更新后的数组所需的最小戈比数。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n \leq 10^5, 0 \leq q \leq 10^5)$ —— 分别表示数组 $a$ 的长度和修改次数。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ $(1 \leq a_i \leq 10^9)$ —— 数组 $a$ 的初始元素。

接下来的 $q$ 行，每行包含两个整数 $i$ 和 $x$ $(1 \leq i \leq n, 1 \leq x \leq 10^9)$ —— 表示修改的位置和修改后的值。

输出格式

输出 $q + 1$ 个数字 —— 分别对应初始数组和每次修改后的数组所需的最小戈比数。

第一个数字是初始数组 $a$ 的答案。

接下来的 $q$ 个数字是每次修改后的答案。

5 3
20 40 9 25 15
3 10
5 21
4 135

5
25
9
11

4 2
20 4 8 36
1 2
4 18

16
8
8

提示

评分标准

• （8 分）：$n \le 10^2, q = 0$；
• （7 分）：$n \le 10^3, q = 0$；
• （11 分）：$q = 0$；
• （12 分）：$q \leq 100$；
• （9 分）：$q \leq 500$；
• （23 分）：$q \leq 10000$；
• （30 分）：无额外限制。

翻译由 DeepSeek V3 完成