Maximum Weighted Subsequence

You are given a sequence of N positive integers \( A_1,A_2,\ldots,A_N \). For any contiguous subsequence \( A_l,A_{l+1},\ldots,A_r \), its weight is defined as:

\( W(l,r) = (r-l+1)\times \gcd(A_l,A_{l+1},\ldots,A_r) \)

Your task is to determine the maximum weight among all contiguous subsequences.

inputFormat

The first line contains a single integer N (the length of the sequence).

The second line contains N positive integers \( A_1, A_2,\ldots, A_N \) separated by spaces.

outputFormat

Output a single integer — the maximum weight among all contiguous subsequences.

sample

3
4 8 2

8