Kí hiệu ~GCD(x, y)~ là ước chung lớn nhất của hai số nguyên dương ~x~ và ~y~.

Cho dãy ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~. Hãy tìm giá trị lớn nhất có thể của biểu thức ~GCD(a_i, a_j) + GCD(a_k, a_t)~, trong đó bốn chỉ số thỏa mãn ~1 \le i < j < k < t \le n~.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ (~3 < n \le 10^5~) là độ dài dãy ~a~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^5~).

Kết quả

Ghi ra một số nguyên duy nhất là giá trị lớn nhất tìm được.

Ví dụ

GCD.INP

6
8 12 4 20 30 15

GCD.OUT

19

Giải thích: chọn các chỉ số 1, 3, 5, 6 ta được ~GCD(a_1, a_3) + GCD(a_5, a_6) = 4 + 15 = 19~, đây là giá trị lớn nhất.

Giới hạn

• Subtask 1 (30% số điểm): ~n \le 50~.
• Subtask 2 (30% số điểm): ~n \le 10^3~.
• Subtask 3 (40% số điểm): không có ràng buộc gì thêm.