题目描述

There are $N$ cards in a deck, numbered from $1$ to $N$, where card $i$ has a positive integer $A_i$ written on it.

You are to perform $N - 1$ moves with the cards. In each move, you select two cards of your choice from the deck. Let $x$ and $y$ be the integers written on the selected cards, respectively. Remove both selected cards, and insert a new card into the deck with $2 \cdot \gcd(x, y)$ written on it, where $\gcd(x, y)$ is the greatest common divisor of $x$ and $y$. Note that with this one move, there will be one fewer card in the deck (as you remove two cards and insert one new card).

After all $N - 1$ moves have been performed, there will be exactly one card remaining. Your goal is to maximize the integer written on the last card; output this integer.

输入格式

Input begins with an integer $N$ ($2 \leq N \leq 100\,000$) representing the number of cards. The next line contains $N$ integers $A_i$ ($1 \leq A_i \leq 10^6$) representing the number written on card $i$.

输出格式

Output an integer in a single line representing the maximum possible integer written on the last card.

3
2 4 6

8

3
3 5 7

2

4
9 9 9 9

36

5
10 100 1000 10000 100000

160

提示

Explanation for the sample input/output #1

To get the maximum possible integer on the last card, you have to select card $1$ and card $3$ on the first move with $x = 2$ and $y = 6$. Remove both selected cards, and insert a new card with $2 \cdot \gcd(2, 6) = 4$ written on it. For the second move, there are two cards remaining with an integer $4$ written on each card. Select those cards with $x = 4$ and $y = 4$. Remove both selected cards, and insert a new card with $2 \cdot \gcd(4, 4) = 8$ written on it. The last card has an integer $8$ written on it, and it is the maximum possible integer in this example.

Explanation for the sample input/output #2

Regardless of your choice in each move, the answer will always be $2$.