说明

有一副包含 $N$ 张卡牌的牌堆，卡牌编号从 $1$ 到 $N$，其中卡牌 $i$ 上写有一个正整数 $A_i$。

你需要对卡牌进行 $N - 1$ 次操作。在每次操作中，你从牌堆中任意选择两张卡牌。设所选两张卡牌上写的整数分别为 $x$ 和 $y$。移除这两张被选中的卡牌，并向牌堆中插入一张新卡牌，其上写有 $2 \cdot \gcd(x, y)$，其中 $\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数。注意，经过这样一次操作后，牌堆中的卡牌数量会减少一张（因为你移除了两张卡牌并插入了一张新卡牌）。

在所有 $N - 1$ 次操作完成后，牌堆中将恰好剩下一张卡牌。你的目标是使最后一张卡牌上写的整数尽可能大；请输出这个整数。

输入格式

输入以一个整数 $N$（$2 \leq N \leq 100\,000$）开始，表示卡牌的数量。接下来一行包含 $N$ 个整数 $A_i$（$1 \leq A_i \leq 10^6$），表示卡牌 $i$ 上写的数字。

输出格式

在一行中输出一个整数，表示最后一张卡牌上可能的最大整数。

3
2 4 6

8

3
3 5 7

2

4
9 9 9 9

36

5
10 100 1000 10000 100000

160

提示

样例输入/输出 #1 的解释

为了获得最后一张卡牌上可能的最大整数，你必须在第一次操作中选择卡牌 $1$ 和卡牌 $3$，此时 $x = 2$，$y = 6$。移除这两张选中的卡牌，并插入一张写有 $2 \cdot \gcd(2, 6) = 4$ 的新卡牌。第二次操作时，剩余两张卡牌，每张上都写有整数 $4$。选择这两张卡牌，此时 $x = 4$，$y = 4$。移除这两张选中的卡牌，并插入一张写有 $2 \cdot \gcd(4, 4) = 8$ 的新卡牌。最后一张卡牌上写的整数是 $8$，这是本例中可能的最大整数。

样例输入/输出 #2 的解释

无论你在每次操作中如何选择，答案始终是 $2$。

翻译由 DeepSeek 完成