Problem Background

Poor $\texttt{MhxMa}$ originally wanted to come up with this problem, but it was already taken by $\texttt{tymRocket}$. Now, $\texttt{MhxMa}$ sits in front of the computer, staring at the nearly completed data, imagining the shattered dream of his problem stumping a large number of contestants.

Problem Description

This is a jump game. In the game, you can jump to any position, where there are $n$ points: $1, 2, 3, \cdots, n$, and jumping to each point will earn you reward points $a_1, a_2, \cdots, a_n$.

Obviously, the game is simple, and $\texttt{MhxMa}$ quickly earned all the points. He then improved the code by adding an experience value parameter.

For the $n$ points with reward points, if you jump from point $x$ to point $y$, you will earn experience points $\operatorname{score}_{x, y}(1 \le x \le y \le n)$:

$$ \operatorname{score}_{x, y} = \begin{cases} \operatorname{len} & \operatorname{gcd}(a_x, a_{x+1}, \dots, a_y) = 2, \operatorname{len} \mod 2 = 0 \\ \operatorname{len} & \operatorname{gcd}(a_x, a_{x+1}, \dots, a_y) = 3, \operatorname{len} \mod 2 = 1 \\ 0 & \operatorname{others} \end{cases} $$

where $\operatorname{len}$ represents the length of the interval, which is $y - x + 1$.

For each pair of positions $(x, y)$, multiple jumps will only earn you experience points once.

To showcase your programming skills to $\texttt{MhxMa}$, you decide to write a code to calculate the maximum experience points that can be earned in this game.

Input Format

The input consists of two lines.

The first line contains an integer $n$.

The second line contains $n$ integers $a_i$.

Output Format

Output a single integer, which is the answer.

Sample Input and Output

Sample Input #1

5
2 3 6 3 9

Sample Output #1

8

Sample Input #2

5
2 2 2 2 2

Sample Output #2

16

Sample Input #3

9
6 2 3 6 4 6 8 2 5

Sample Output #3

19

Notes

Sample Explanation #1

$\operatorname{score}_{2, 2} = 1$.

$\operatorname{score}_{2, 4} = 3$.

$\operatorname{score}_{3, 5} = 3$.

$\operatorname{score}_{4, 4} = 1$.

$1 + 3 + 3 + 1 = 8$.

Sample Explanation #2

$\operatorname{score}_{1, 2} = 2$.

$\operatorname{score}_{1, 4} = 4$.

$\operatorname{score}_{2, 3} = 2$.

$\operatorname{score}_{2, 5} = 4$.

$\operatorname{score}_{3, 4} = 2$.

$\operatorname{score}_{4, 5} = 2$.

$2 + 4 + 2 + 4 + 2 + 2 = 16$.

Data Size and Constraints

This problem uses batched testing.

• Subtask 0 (20 pts): $n \le 10^2$.
• Subtask 1 (10 pts): $n \le 2 \times 10^3$.
• Subtask 2 (20 pts): $n \le 10^4$.
• Subtask 3 (50 pts): $n \le 6 \times 10^5$.

For all test cases, $1 \le n \le 6 \times 10^5$, $1 \le a_i \le 10^7$.

见题面 Input 部分

见题面 Output 部分