Description

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.

Input Format

The input contains one line with a positive integer $N$.

The next line contains $N$ positive integers, representing the sequence $A_i$.

Output Format

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

5
30 60 20 20 20

80

Hint

$1 \le A_i \le 10^{12}, 1 \le N \le 100000$

Translated by ChatGPT 5