Problem F
LCM Thief
There are $n$ numbers hidden in the vault of the intergalactic hall of numbers. Visitors to the hall can see the least common multiple (LCM) of these numbers as part of the exhibit. Recall that the LCM of $n$ numbers $x_1,x_2,\dots ,x_ n$ is the smallest positive integer which is divisible by $x_1,x_2,\dots $ and $x_ n$. As you are a member of the thieves guild, you would like to steal one of these numbers for yourself. However, you must be careful about which number you steal, because if the number you steal decreases the LCM too much, the guards may become suspicious.
Given the list of numbers in the vault, pick a number to steal that maximizes the LCM of the $n-1$ remaining numbers.
Input
The first line of input contains an integer $n$ ($3\le n\le 10^5$) indicating how many numbers are in the vault. The next $n$ lines each contain one of the numbers from the vault. The numbers will all be integers between $1$ and $10^6$.
Output
Output the number that you should steal. If there are multiple optimal choices, output the smallest one.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 2 8 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 24 7 8 31 |
8 |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 13 18 23 28 33 38 |
18 |
