Background

The poor $\texttt{MhxMa}$ originally came up with this problem, but it was already taken by $\texttt{Ferm\_Tawn}$. At this moment, $\texttt{MhxMa}$ sat in front of the computer, looking at the testdata that was almost ready, imagining his dream of having his problem stump a large number of contestants shattering.

Problem Description

This is a jumping game. In the game, you can jump to any position. There are $n$ points: $1, 2, 3, \cdots, n$. Jumping there gives you reward scores $a_1, a_2, \cdots, a_n$.

Obviously, this game is very easy. $\texttt{MhxMa}$ got all the scores in no time, so he improved the code by adding a parameter called experience points.

For the $n$ points with reward scores, if you jump from point $x$ to point $y$, you will gain 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} &\gcd(a_x , a_{x + 1} , \dots , a_y)=3 , \operatorname{len \ mod} 2 = 1\\ 0 & \operatorname{others} \end{cases}$$

Here, $\operatorname {len}$ denotes the length of the interval, i.e., $y-x+1$.

For each pair of positions $(x,y)$, jumping multiple times will only grant experience points once.

To show $\texttt{MhxMa}$ your programming skills, you decide to write a program to compute the maximum total experience points that can be obtained in this game.

Input Format

The input has two lines.

The first line contains an integer $n$.

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

Output Format

Output one integer, representing the answer.

5
2 3 6 3 9

8

5
2 2 2 2 2

16

9
6 2 3 6 4 6 8 2 5

19

Hint

Please use a fast input method.

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$.

---

Constraints

This problem uses bundled tests.

• 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 testdata, $1 \le n \le 6 \times 10^5$, $1 \le a_i \le 10^7$.

Translated by ChatGPT 5