P15621 [ICPC 2022 Jakarta R] Doubled GCD

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.

#### 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$.