题目描述

在一次又一次的「回天」中，晓美焰不断改写着世界的因果。

她手中有一个长度为 $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$ 行输出该次修改完成后序列的混乱度。

4
2 2 3 3
2
3 2
4 4

5
5
6

提示

样例中每次修改后的序列及一种最优划分方案如下：