「XSOI-R1」跳跃游戏

本来可怜的 $\texttt{MhxMa}$ 想出这道题，但是已经被 $\texttt{Ferm\_Tawn}$ 抢了，此时 $\texttt{MhxMa}$ 坐在电脑面前，看着马上要造好的数据，想象着自己的题难倒一大片选手的梦想破灭了。

这是一个跳跃游戏。在游戏中你可以跳到任意位置，其中有 $n$ 个点：$1 , 2 , 3, \cdots , n$，跳到那里会有奖励分数 $a_1 , a_2 , \cdots , a_n$。 显然，这个游戏很简单，$\texttt{MhxMa}$ 没过多久就获得了所有分数，于是改进了代码，添加了经验值这个参数。 对于有奖励分数的 $n$ 个点，若从点 $x$ 跳到点 $y$，会获得经验值 $\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}$$ 其中，$\operatorname {len}$ 表示区间的长度，即 $y-x+1$。 **对于每一对位置 $(x,y)$，多次跳跃只会获得一次经验值。** 为了向 $\texttt{MhxMa}$ 展现你的编程实力，你决定写一个代码算出这个游戏能刷到的最大经验值。

输入共两行。 输入第一行包含一个整数 $n$。 第二行包含 $n$ 个整数 $a_i$。

输出一个整数，表示答案。

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

**请使用较快的读入方式。** ### 样例解释 #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$。 ### 样例解释 #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$。 ------------ ### 数据规模与约定 **本题采用捆绑测试**。 - 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 $。 对于所有测试数据，$1 \le n \le 6 \times 10^5$，$1 \le a_i \le 10^7$。