Problem Brief

Find Maximum Possible GCD 🥭

You are given an integer R, and an array A consisting of positive integers. You can do this operation at most once (possibly zero times):

Choose any element of the array. Replace it with any integer X, such that 1 ≤ X ≤ R.

Find the maximum possible GCD of the entire array.

Constraints:

1Example 1

Input

R = 10, A = [2, 3, 4]

Output

Explanation

We can change the second element from 3 to 2. Then GCD of the array becomes gcd(2,2,4)=2, which is the maximum possible.

Limits and guarantees your solution can rely on.

2 ≤ N ≤ 10^5 (N is length of array)

1 ≤ R ≤ 10^5

1 ≤ Ai ≤ 10^5

Draft autosaves locally

public int findMaximumPossibleGCD(int R, int[] A) {
    // write your code here
}

Input

[2, 3, 4]

Output