P5502 [JSOI2015] Greatest Common Divisor

Given a sequence of positive integers $A_i$ of length $N$. For any consecutive subsequence $A_l, A_{l+1}, ..., A_r$, define its weight $W(L, R)$ as the product of its length and the greatest common divisor of all elements in the subsequence, i.e., $W(L, R) = (R - L + 1) × \gcd(A_l, ..., A_r)$. `JYY` wants to find the subsequence with the maximum weight.

The input contains one line with a positive integer $N$. The next line contains $N$ positive integers, representing the sequence $A_i$.

Output one line with a positive integer, representing the maximum weight among all subsequences.

$1 \le A_i \le 10^{12}, 1 \le N \le 100000$ Translated by ChatGPT 5