Kozak Vus and NSD#10447
Cossack Vus has an array consisting of integers. He learns about another array , which also has integers, but he doesn't know the values of . To determine the array , Vus can perform the following operation any number of times:
Select two integers 1 \leq l \leq r \leq n.
Discover the sum b_l + b_{l + 1} + \dots + b_r.
Pay gcd(a_l, a_{l+1}, ..., a_r) coins, where is the greatest common divisor (e.g., gcd(3, 5) = 1, and gcd(15, 30, 6) = 3).
Vus wants you to find the minimum number of coins needed to determine the array .
Additionally, Vus will change a certain number a_i to a total of times. After each change, you need to find the minimum number of coins required for the updated array.
The first line contains two integers and (1 \leq n \leq 10^5, 0 \leq q \leq 10^5) — the number of elements in the array and the number of changes to the array.
The second line contains integers a_1, a_2, ..., a_n (1 \leq a_i \leq 10^9) — the elements of the array.
The next lines each contain two integers and (1 \leq i \leq n, 1 \leq x \leq 10^9) — the index of the element in the array that is changed and the new value it is changed to.
Output q + 1 numbers — for each version of the array , find the minimum number of coins needed to determine the array .
The first number is the answer for the initial array .
The next numbers are the answers for each update of the array.
Example 1
Example 2
( points): n \le 10^2, q = 0;
( points): n \le 10^3, q = 0;
( points): q = 0;
( points): q \leq 100;
( points): q \leq 500;
( points): q \leq 10000;
( points): no additional constraints.