There are N integers, A_1, A_2, ..., A_N, written on the blackboard.

You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), possibly the same as the integer originally written.

Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Constraints

* All values in input are integers.
* 2 \leq N \leq 10^5
* 1 \leq A_i \leq 10^9

Output

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N

Output

Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Examples

Input

3
7 6 8


Output

2


Input

3
12 15 18


Output

6


Input

2
1000000000 1000000000


Output

1000000000
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] nums = new int[(int) Math.ceil(Math.log(n) / Math.log(2))+1][n+1];
        int[] lengths=new int[nums.length];
        lengths[0]=n;
        for(int i=0;i<n;i++){
            nums[0][i]=sc.nextInt();
        }
        for(int i=1;i<nums.length;i++){
            lengths[i]=lengths[i-1]%2==0?lengths[i-1]/2:lengths[i-1]/2+1;
            for(int j=0;j<lengths[i-1]/2;j++){
                nums[i][j]=Euclid(nums[i-1][j*2],nums[i-1][j*2+1]);
            }
            if(lengths[i-1]%2==1){
                nums[i][lengths[i-1]/2]=nums[i-1][lengths[i-1]-1];
            }
        }
        int output=1;
        int tmp;
        int now;
        for(int i=0;i<n;i++){
            now=i;
            tmp=0;
            for(int j=0;j<nums.length;j++){
                tmp=Euclid(tmp,nums[j][now%2==0?now+1:now-1]);
                now=now/2;
            }
            output=Math.max(tmp,output);
        }
        System.out.println(output);
    }

    private static int Euclid(int n, int m) {
        int tmp;
        if(n==0||m==0){
            return Math.max(n,m);
        }
        while (true) {
            if (n == 0) {
                return m;
            } else if (m == 0) {
                return n;
            }
            tmp = n;
            n = m;
            m = tmp;
            n = n % m;

        }
    }
}