P10403 "XSOI-R1" Jumping Game

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.

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.

The input has two lines. The first line contains an integer $n$. The second line contains $n$ integers $a_i$.

Output one integer, representing the answer.

**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