Chọn ĐTQG Quảng Trị 2026 - Bài 1 : Điểm ổn định

Sau một đợt thiên tai lớn, nhiều khu vực bị chia cắt và hệ thống thông tin liên lạc bị ảnh hưởng. Trung tâm điều hành cứu trợ triển khai một hệ thống hỗ trợ thông minh nhằm nhanh chóng đánh giá hiện trạng, duy trì liên lạc và tổ chức vận chuyển vật tư đến các khu vực cần thiết.

Trước tiên, trung tâm muốn đánh giá mức độ ổn định của hệ thống hỗ trợ thông qua các tín hiệu được truyền về từ các thiết bị. Điểm ổn định của hệ thống càng cao thì việc truyền tin có độ tin cậy càng lớn.

Hệ thống gồm \(N\) thiết bị được đánh số thứ tự từ \(1\) đến \(N\) và bố trí tại \(N\) khu vực khác nhau, mỗi khu vực bố trí \(1\) thiết bị. Thiết bị thứ \(i\) truyền về cho trung tâm một tín hiệu mang giá trị là một số nguyên dương \(A_i\), các giá trị này được lưu thành một dãy theo thứ tự từ \(A_1\) đến \(A_N\). Với một đoạn các giá trị liên tiếp trong dãy từ vị trí \(L\) đến vị trí \(R\), nhịp đồng bộ của đoạn được tính là \(G(L,R) = \gcd(A_L, A_{L+1}, \ldots, A_R)\), trong đó \(\gcd(A_L, A_{L+1}, \ldots, A_R)\) là ước chung lớn nhất của các giá trị \(A_L, A_{L+1}, \ldots, A_R\). Điểm ổn định của đoạn được xác định bởi \(F(L,R) = G(L,R) \times (R-L+1)\). Điểm ổn định của hệ thống là \(\max(F[L,R])\) với \(1 \le L \le R \le N\).

Yêu cầu: Hãy tìm điểm ổn định của hệ thống.

Input

• Dòng \(1\) chứa số nguyên \(N\) \((1 \le N \le 2 \times 10^5)\).
• Dòng \(2\) chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) \((1 \le A_i \le 10^9; 1 \le i \le N)\).

Output

• Ghi ra một dòng chứa một số nguyên dương là điểm ổn định của hệ thống tìm được.

Example

6
12 17 14 18 18 3

36

Scoring

• Subtask 1 (\(20\) điểm): \(N \le 300\).
• Subtask 2 (\(25\) điểm): \(N \le 5000\).
• Subtask 3 (\(25\) điểm): \(A_{i+1}\) chia hết cho \(A_i\) với mọi \(1 \le i < N\).
• Subtask 4 (\(30\) điểm): Không có ràng buộc gì thêm.