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.Scanner;

public class Main {

	static Scanner scanner;
	static int n;
	static int[] A;
	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    n=gi();
	    A=new int[n];
	    for(int i=0; i<n;i++) {
	    	A[i]=gi();
	    }

	    int a=g(0, n-1, 0);
//	    if (s>x) {
//	    	System.out.println(n-1);
//	    } else {
//	    	Arrays.parallelSort(a);
//
//	    	System.out.println(c);
//	    }
	    System.out.println(a);
	}

	public static int g(int l, int r, int m) {
        if(r-l<1) return m;
		int l1=l;
		int r1=Math.floorDiv((l+r),2);
		int l2=r1+1;
		int r2=r;
		int u1=f(l1, r1, m);
		int u2=f(l2, r2, m);
		if(u1>u2) {
			return g(l2, r2, u1);
		} else if(u1<u2) {
			return g(l1, r1, u2);
		} else {
			return u1;
		}
	}

	public static int f(int l, int r, int m) {
		int u=A[l];
		for(int i=l+1; i<=r;i++) {
			u=uclid(u,A[i]);
		}
		if(m!=0) {
			u=uclid(u,m);
		}

		return u;
	}

	// ユークリッドの互除法
    public static int uclid(int m, int n) {
    	if (m<n) {
			m^=n;
			n^=m;
			m^=n;
		}

		while(true) {
			int t=m%n;
			if (t==0) {
				return n;
			} else {
				m=n;
				n=t;
			}
		}
    }


	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}