RoAlgo Contest #10 | vecinul

Task

The neighbor received a sequence of $n$ numbers from a friend. He wants to split the sequence into subarrays of length at least $2$ so that each number in the sequence appears in exactly one subarray. He then calculates the greatest common divisor of the numbers in each subarray and sums up the results, resulting in a sum $S$.

The neighbor realizes that he can obtain different sums $S$ depending on how he splits the sequence into subarrays. Help the neighbor find out the maximum possible sum $S$ he can obtain.

Input data

The first line contains the number $n$. The second line contains $n$ numbers separated by spaces, representing the numbers in the sequence.

Due to the size of the input data, it is recommended to add these lines at the beginning of the main() function:

ios_base::sync_with_stdio(0);
cin.tie(0);

Output data

The first line will contain a single integer, the maximum possible sum $S$.

Constraints and clarifications

• $2 \leq n \leq 200\ 000$;
• $1 \leq x \leq 2\ 000\ 000$, where $x$ is a number in the sequence;

Example

stdin

5
6 2 3 1 4

stdout

3

Explanation

The first subarray will consist of the numbers $6, 2$; $gcd(6, 2) = 2$
The second subarray will consist of the numbers $3, 1, 4$; $gcd(3, 1, 4) = 1$
$S = 2 + 1 = 3$
A higher sum cannot be obtained.