Cho mảng ~a~ gồm ~n~ số nguyên được đánh số từ ~1~ đến ~n~. Bạn có thể thực hiện thao tác sau tối đa một lần:

• Chọn một số nguyên ~a_i~ từ mảng, chọn một số nguyên ~x~ trong khoảng từ ~1~ đến ~10^9~, thay thế ~a_i=x~.

Bạn hãy xác định giá trị lớn nhất của ~gcd(a_1,a_2,..,a_n)~ sau khi thực hiện thao tác trên tối đa một lần.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên mảng ~a~ ~(1 \le a_i \le 10^9)~.

Output

• In ra giá trị lớn nhất của ~gcd(a_1,a_2,..,a_n)~ sau khi thực hiện thao tác trên tối đa một lần.

Examples

Sample Input 1

3
2 3 4

Sample Output 1

2

Sample Input 2

4
1 2 3 4

Sample Output 2

1

Notes

Trong ví dụ đầu tiên, thực hiện thao tác thay thế ~a_2=8~ và ~gcd(a_1,a_2,a_3)=gcd(2,8,4)=2~.