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();
        List<Integer> valueList = new ArrayList<>();
        for (int i=0; i<n; i++){
            valueList.add(sc.nextInt());
        }

        if (n == 2){
            System.out.println(Math.max(valueList.get(0), valueList.get(1)));
        }else {
            int[] leftGCM = new int[n];
            int[] rightGCM = new int[n];

            for (int i=0; i<n; i ++){
                if (i == 0){
                    leftGCM[0] = valueList.get(0);
                    rightGCM[n-1] = valueList.get(n-1);
                }else {
                    leftGCM[i] = getGCM(valueList.get(i), leftGCM[i-1]);
                    rightGCM[n-1-i] = getGCM(valueList.get(n-1-i), rightGCM[n-i]);
                }
            }

            int maxGCM = 1;
            for (int i=0; i<n; i++){
                if (i == 0){
                    int gcm = rightGCM[i+1];
                    if (gcm > maxGCM){
                        maxGCM = gcm;
                    }
                }else if (i == n-1){
                    int gcm = leftGCM[i-1];
                    if (gcm > maxGCM){
                        maxGCM = gcm;
                    }
                }else {
                    int gcm = getGCM(leftGCM[i-1], rightGCM[i+1]);
                    if (gcm > maxGCM){
                        maxGCM = gcm;
                    }
                }
            }

            System.out.println(maxGCM);

        }
    }

    private static int getGCM(int a, int b){
        int larger = Math.max(a, b);
        int gcm = Math.min(a, b);

        if (gcm == 0){
            return larger;
        }

        while (larger % gcm != 0){
            int smaller = gcm;
            gcm = larger % gcm;
            larger = smaller;
        }

        return gcm;
    }
}