{"raw_statement":[{"iden":"background","content":"本来可怜的 $\\texttt{MhxMa}$ 想出这道题，但是已经被 $\\texttt{Ferm\\_Tawn}$ 抢了，此时 $\\texttt{MhxMa}$ 坐在电脑面前，看着马上要造好的数据，想象着自己的题难倒一大片选手的梦想破灭了。"},{"iden":"statement","content":"这是一个跳跃游戏。在游戏中你可以跳到任意位置，其中有 $n$ 个点：$1 , 2 , 3, \\cdots , n$，跳到那里会有奖励分数 $a_1 , a_2 , \\cdots , a_n$。\n\n显然，这个游戏很简单，$\\texttt{MhxMa}$ 没过多久就获得了所有分数，于是改进了代码，添加了经验值这个参数。\n\n对于有奖励分数的 $n$ 个点，若从点 $x$ 跳到点 $y$，会获得经验值 $\\operatorname{score}_{x , y}(1\\le x\\le y\\le n)$：\n\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}$$\n\n其中，$\\operatorname {len}$ 表示区间的长度，即 $y-x+1$。\n\n**对于每一对位置 $(x,y)$，多次跳跃只会获得一次经验值。**\n\n为了向 $\\texttt{MhxMa}$ 展现你的编程实力，你决定写一个代码算出这个游戏能刷到的最大经验值。"},{"iden":"input","content":"输入共两行。\n\n输入第一行包含一个整数 $n$。\n\n第二行包含 $n$ 个整数 $a_i$。"},{"iden":"output","content":"输出一个整数，表示答案。"},{"iden":"note","content":"**请使用较快的读入方式。**\n\n### 样例解释 #1\n\n$\\operatorname{score_{2 , 2}}= 1$。\n\n$\\operatorname{score_{2 , 4}}= 3$。\n\n$\\operatorname{score_{3 , 5}}= 3$。\n\n$\\operatorname{score_{4 , 4}}= 1$。\n\n$1+3+3+1=8$。\n\n### 样例解释 #2\n\n$\\operatorname{score_{1 , 2}}= 2$。\n\n$\\operatorname{score_{1 , 4}}= 4$。\n\n$\\operatorname{score_{2 , 3}}= 2$。\n\n$\\operatorname{score_{2 , 5}}= 4$。\n\n$\\operatorname{score_{3 , 4}}= 2$。\n\n$\\operatorname{score_{4 , 5}}= 2$。\n\n$2+ 4 + 2 + 4 + 2 + 2 = 16$。\n\n------------\n### 数据规模与约定\n\n**本题采用捆绑测试**。\n\n- Subtask 0（20 pts）：$n \\le 10^2$。 \n\n- Subtask 1（10 pts）：$n \\le 2 \\times 10^3$。\n\n- Subtask 2（20 pts）：$n \\le 10^4$。\n\n- Subtask 3（50 pts）：$n \\le 6 \\times 10^5 $。\n\n\n对于所有测试数据，$1 \\le n \\le 6 \\times 10^5$，$1 \\le a_i \\le 10^7$。"}],"translated_statement":null,"sample_group":[["5\n2 3 6 3 9","8"],["5\n2 2 2 2 2","16"],["9\n6 2 3 6 4 6 8 2 5","19"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}