GCDChel Loves GCD

Time limit1sMemory limit1024 MB

Summary

Given an array, repeatedly split off either the left floor(n/2) elements or the right ceil(n/2) elements, sum the GCDs of the removed blocks, and maximize that sum.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Math, Number theory
Solved: No attempts yet

Problem

Sicheol wants to find the most beautiful studio apartment in Sinchon. Too busy to visit rooms in person, he plans to predict a studio's beauty from its listing number and the greatest common divisor (GCD). The beauty is computed as follows.

There is an integer array $S$ of listing numbers. ( $|S| = N$ , where $|S|$ is the number of elements of $S$ )
Choose $\lfloor \frac{|S|}{2} \rfloor$ elements from the left of $S$ , or $\lceil \frac{|S|}{2} \rceil$ elements from the right. If $S$ has exactly one element, choose that element.
Compute the $GCD$ of the chosen elements.
Let $S'$ be the array of elements not chosen, and repeat from step 2.
The beauty of the studio is the maximum possible sum of the $GCD$ values obtained in step 3.

Compute the beauty of the studio from the listing numbers!

Input

The first line gives an integer $N$ . ( $1 \leq N \leq 200\,000$ )

The second line gives integers $a_1, a_2, \cdots, a_N$ , the listing numbers of the studio. ( $1 \leq a_i \leq 200\,000$ )

Output

Print the beauty of the studio.

Examples2

Example 1
Input
```
4
4 4 4 4
```
Expected output
```
12
```
Example 2
Input
```
5
1 2 3 4 5
```
Expected output
```
13
```