B - Maximum GCD Sum

Time limit: 2 s
Memory limit: 1024 MiB
Languages: C, C++, Java, Python, ... (details)

For two positive integers $a$ and $b$, let $gcd(a, b)$ be the greatest common divisor of $a$ and $b$, that is, the largest integer that divides both $a$ and $b$ (leaving no remainder).

Let's extend the definition of gcd to a sequence $S = s_1, s_2, ..., s_k$, where $k > 2$ as follows:  $gcd(S) = gcd(s_1, gcd({s_2, ..., s_{k-1}, s_k}))$. That is,  gcd of a sequence is the gcd of the first element in the sequence and the gcd of the rest of the sequence.

For a sequence $S$ consisting of at least two integers, let's define a function $F(S) = |S| \times gcd(S)$, where $|S|$ is the length of the sequence.

Given an array $A$, determine what is the maximum possible value of $F(S)$ where $S$ is a subsequence of $A$ with at least two elements.

A sequence $S$ is a subsequence of an array $A$ if $S$ can be obtained from $A$ by erasing several (possibly zero or all) elements.


The first line of the input contains integer $n$ $(2 \leq n \le 10^5$), representing the length of the array $A$.

The second line contains $n$ positive integers $a_1$, $a_2$, ... , $a_n$ not exceeding $10^6$, corresponding to the elements in the sequence $A$ .


Print a single line with the maximum value of $F(S)$ where $S$ is a subsequence of array $A$ with at least two elements.

Sample test(s)

7 10 6 1 30 5 42 6
2 3 10
6 1 20 30 50 70 5