GGCD - MarisaOJ: Marisa Online Judge

GGCD

Time limit: 1000 ms
Memory limit: 256 MB
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$.