Chu kỳ đồng bộ chung mạnh nhất

Bối cảnh và bài toán

Mỗi thiết bị trong một cụm có một chu kỳ đồng bộ nguyên x[i]. Hai thiết bị có thể chạy chung một nhịp nếu nhịp đó chia hết cả hai chu kỳ. Đội vận hành muốn chọn hai thiết bị sao cho nhịp đồng bộ chung lớn nhất có thể.

Số thiết bị và miền chu kỳ đều lớn, nên xét mọi cặp là không khả thi.

Yêu cầu

Tìm giá trị lớn nhất có thể của gcd(x[i], x[j]) với i != j.

Input

• Dòng 1: số nguyên n.
• Dòng 2: n số nguyên dương x[i].

Output

In một số nguyên — GCD lớn nhất của một cặp phần tử khác vị trí.

Ràng buộc

• 2 <= n <= 2 * 10^5
• 1 <= x[i] <= 10^6

Chấm điểm

Ví dụ 1

Input

5
3 14 15 7 9

Output

7

Giải thích. Cặp 14 và 7 có GCD bằng 7, và không có cặp nào đạt GCD lớn hơn.

Ví dụ 2

Input

4
8 12 16 20

Output

8

Giải thích. Cặp 8 và 16 có GCD bằng 8.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Common Divisors (Task 1081). Tham khảo: https://cses.fi/problemset/task/1081/