Doubled GCD

Time limit2sMemory limit1024 MB

Summary

Given N numbers, repeatedly replace two cards x and y with 2 * gcd(x, y) until one card is left, and find the largest possible final value.

Level: Medium6 of 10
Topics: Number theory, Math, Bit manipulation
Solved: No attempts yet

Problem

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

You perform $N - 1$ moves with the cards. In each move, you select two cards from the deck. Let $x$ and $y$ be the integers on the selected cards. Remove both cards and insert a new card with $2 \cdot \gcd(x, y)$ written on it, where $\gcd(x, y)$ is the greatest common divisor of $x$ and $y$ . Each move leaves one fewer card in the deck, since two cards are removed and one is inserted.

After all $N - 1$ moves, exactly one card remains. Find the maximum possible integer on the last card and output it.

Input

The first line contains an integer $N$ ( $2 \le N \le 100\,000$ ), the number of cards. The next line contains $N$ integers $A_1, A_2, \ldots, A_N$ ( $1 \le A_i \le 10^9$ ), where $A_i$ is the number written on card $i$ .

Output

Output the maximum possible integer on the last card on a single line.

Examples4

Example 1
Input
```
3
2 4 6
```
Expected output
```
8
```
Example 2
Input
```
3
3 5 7
```
Expected output
```
2
```
Example 3
Input
```
4
9 9 9 9
```
Expected output
```
36
```
Example 4
Input
```
5
10 100 1000 10000 100000
```
Expected output
```
160
```