P17846 回天

在一次又一次的「回天」中，晓美焰不断改写着世界的因果。 她手中有一个长度为 $n$ 的序列。每个时刻，晓美焰都会修改其中某个位置的值；而鹿目圆则会在修改后观测当前的序列，并计算这个序列的混乱值。 对于一个序列，将其中的所有元素划分为两个**非空**可重集 $A,B$。定义可重集 $S$ 的价值为其中所有元素的最大公约数，即 $f(S)=\gcd \limits_{x\in S}x$。 序列的混乱值定义为所有划分方式中 $f(A)+f(B)$ 的最大值。 请你帮助鹿目圆，在晓美焰每次修改序列后，计算出当前序列的混乱值。

第一行一个整数 $n$（$2 \leq n \leq 2 \times 10^5$），表示晓美焰手中序列的长度。 第二行 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^9$），表示序列的初始状态。 第三行一个整数 $q$（$1 \leq q \leq 10^5$），表示修改次数。 接下来 $q$ 行，每行两个整数 $i$（$1 \leq i \leq n$）和 $v$（$1 \leq v \leq 10^9$），表示将 $a_i$ 的值修改为 $v$。

输出 $q+1$ 行。 第一行输出序列在进行任何修改之前的混乱度。 对于第 $i$ 次修改，第 $i+1$ 行输出该次修改完成后序列的混乱度。

样例中每次修改后的序列及一种最优划分方案如下： | 当前序列 | 最优划分方案 | | --- | --- | | $2,2,3,3$ | $A=\{2,2\},\ B=\{3,3\}$，混乱值为 $2+3=5$ | | $2,2,2,3$ | $A=\{2,2,2\},\ B=\{3\}$，混乱值为 $2+3=5$ | | $2,2,2,4$ | $A=\{2,2,2\},\ B=\{4\}$，混乱值为 $2+4=6$ |