Ngày hôm ấy p2o2HuaGiaBao đi trong mưa, thế nhưng lại quên tim không khóa cửa
Để cho mưa lân la hỏi thăm, lẻn vào trộm đi khế ước trăm năm
Ngày p2o2HuaGiaBao đi theo cơn mưa ngâu, bầy chim lạc cánh khóc hoảng tìm nhau
Ai đong ai đếm hết bao hard-problem ...

Nhân dịp mùa mưa (mùa dễ thất tình), p2o2HuaGiaBao tặng cho dinh (học sinh của anh ấy) một món quà chính là bài tập khá chill này:
Cho dãy số nguyên dương \(A\) gồm \(N\) số nguyên dương là: \(A_1,A_2,A_3,...,A_N\). Hãy tìm \(gcd(a_i,a_j)_{\text{max}}\) với \((1\le i < j\le n)\).
Mà vì trình dinh còn quá gà nên đã code \(O(N^2)\) nên mới nhờ các bạn giúp đỡ.

Input

• Dòng đầu tiên là một số nguyên dương \(N\) (\(1\le N\le 10^5\)).
• Dòng thứ hai là \(N\) số nguyên dương \(A_1,A_2,A_3,...,A_N\) (\(1\le A_i\le 10^5\)).

Output

• Một số nguyên dương là kết quả của bài toán.

Example

5
1 2 3 4 5

2

10
56 78 23 45 89 12 76 69 30 15

23

Scoring

• Subtask \(1\) (\(30\%\)): \(1\le N\le 10^3\)
• Subtask \(2\) (\(70\%\)): Không có ràng buộc gì thêm.