vecinul

Time limit: 0.1s Memory limit: 1MB Input: Output:

Task

The neighbor received a sequence of nn numbers from a friend. He wants to split the sequence into subarrays of length at least 22 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 SS.

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

Input data

The first line contains the number nn. The second line contains nn 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 SS.

Constraints and clarifications

  • 2n200 0002 \leq n \leq 200\ 000;
  • 1x2 000 0001 \leq x \leq 2\ 000\ 000, where xx is a number in the sequence;
# Points Constraints
0 0 Example
1 30 n3 000n \leq 3\ 000
2 70 No additional constraints

Example

stdin

5
6 2 3 1 4

stdout

3

Explanation

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

Log in or sign up to be able to send submissions!