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.io.*;
import java.math.*;
import java.util.*;
public class Main { 
 
	public static void main(String[] args) { 
		Scanner input = new Scanner(System.in);
		int N = input.nextInt();
		long[] pref = new long[N];
		long[] suff = new long[N];
		long[] arr = new long[N];
		for (int i = 0; i < N; i++) {
			arr[i] = input.nextLong();
		}
		pref[0]=arr[0]; //Prefix and suffix sums using a dp approach
		suff[N-1]=arr[N-1];
		for (int i = 1; i < N; i++) {
			long prev = pref[i-1];
			long cur = arr[i];
			pref[i]=GCD(prev,cur);
		}
		for (int i = N-2; i >=0; i--) {
			long prev = suff[i+1];
			long cur = arr[i];
			suff[i]=GCD(prev,cur);
		}
		long ans = pref[N-1]; //Assuming max GCD is GCD of entire tuple to begin with
		ans=Math.max(ans, suff[1]);//Excluding first number
		ans=Math.max(ans, pref[N-2]);//Excluding last number
		for (int cur = 1; cur < N-1; cur++) {
			int prefIndex = cur-1;
			int suffIndex = cur+1;
			long L = pref[prefIndex];
			long R = suff[suffIndex];
			ans=Math.max(ans, GCD(L,R)); //Excluding intermediate elements
		}
		System.out.println(ans);
	}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return Math.max(a, b);
		return GCD(Math.max(a, b)%Math.min(a, b),Math.min(a, b));
	}
}