题目背景

本来可怜的 $\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$。