「XSOI-R1」跳跃游戏

题目背景

本来可怜的 $\texttt{MhxMa}$ 想出这道题,但是已经被 $\texttt{tymRocket}$ 抢了,此时 $\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$。

输出格式


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

输入输出样例

输入样例 #1

5
2 3 6 3 9

输出样例 #1

8

输入样例 #2

5
2 2 2 2 2

输出样例 #2

16

输入样例 #3

9
6 2 3 6 4 6 8 2 5

输出样例 #3

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