|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
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.
Input
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$ .
Output
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)
Input
7
10 6 1 30 5 42 6
Output
24
Input
2
3 10
Output
2
Input
6
1 20 30 50 70 5
Output
40