Description

You are given an array (a₁, a₂, ..., a_n) with each element has integral value. We define the GCD (greatest common divisor) of the array to be the largest positive integer that divides all the elements in the array.

Now, you need to delete a element from the array, determine what is the maximum GCD of this new array can be.

For example, if the given array is [15, 18, 30, 90], then:

• If we delete 15, then the new array is [18, 30, 90], and the GCD is 6
• If we delete 18, then the new array is [15, 30, 90], and the GCD is 15
• If we delete 30, then the new array is [15, 18, 90], and the GCD is 3
• If we delete 90, then the new array is [15, 18, 30], and the GCD is 3

So the answer is 15.

Input

The first line contain an integer n, representing the length of array. 

The second line contain n integers a₁, a₂, ..., a_n, each a_i and a_i+1 are seperated by a blank. 

Constrain

• For testcase 1-4, 1 <= n <= 1000. For testcase 5, n = 200000.
• For each 1 <= i <= n, 1 <= a_i <= 10⁹.

Output

Output the maximum GCD of the array after deleting an element in one line. You need to add '\n' at the end.

Hint

If you use a brute force method to solve the problem, you may get a time limit exceed on testcase5. It may be more suitable to think how to solve testcase5 efficiently after solving other problems.

Sample Input  Download

Sample Output  Download

Tags

Discuss