Task
The neighbor received a sequence of numbers from a friend. He wants to split the sequence into subarrays of length at least 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 .
The neighbor realizes that he can obtain different sums depending on how he splits the sequence into subarrays. Help the neighbor find out the maximum possible sum he can obtain.
Input data
The first line contains the number . The second line contains 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 .
Constraints and clarifications
- ;
- , where is a number in the sequence;
# | Points | Constraints |
---|---|---|
0 | 0 | Example |
1 | 30 | |
2 | 70 | No additional constraints |
Example
stdin
5
6 2 3 1 4
stdout
3
Explanation
The first subarray will consist of the numbers ;
The second subarray will consist of the numbers ;
A higher sum cannot be obtained.