Xây dựng bộ số

Cho dãy số nguyên dương gồm $N$ phần tử $a_1,a_2,\dots ,a_N$.

Yêu cầu: Tìm bộ chỉ số $(i,j,k,t)$ thỏa mãn:

• $i<j<k<t$;
• $gcd(a_i,a_j)+gcd(a_k,a_t)$ lớn nhất.

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

Dữ liệu vào

• Dòng đầu tiên gồm một số nguyên dương $N$;
• Dòng thứ hai gồm $N$ số nguyên dương $a_1,a_2,\dots ,a_N$ $(a_i\le {10}^5)$.

Dữ liệu ra

In ra một số nguyên là giá trị lớn nhất của $gcd(a_i,a_j)+gcd(a_k,a_t)$.

Ràng buộc

• $4<N\le {10}^5$.
• $1\le a_i\le {10}^5$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $4<N\le 50$.
• Subtask 2 ($30\%$ số điểm): $50<N\le 1000$.
• Subtask 3 ($40\%$ số điểm): $1000<N\le {10}^5$.

Ví dụ