For a sequence $a$ consisting of $n$ non-negative elements, replace one element in the sequence $a$ with another non-negative integer such that the greatest common divisor (GCD) of all elements in $a$ is maximized.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $a_i$.
### Output
- Print a single integer, which is the maximum possible GCD of the elements in $a$.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le a_i \le 10^9$.
### Example
Input:
```
3
4 2 8
```
Output:
```
4
```
Explanation:
- Replace the element $2$ with $12$, the GCD of $4$, $12$, and $8$ is $4$.
