#P5502. 最大公约数[JSOI2015]

最大公约数[JSOI2015]

题目描述

给定一个长度为 NN 的正整数序列 AiA_i

对于其任意一个连续的子序列 Al,Al+1,...,ArA_l,A_{l+1},...,A_r ,我们定义其权值 W(L,R)W(L,R) 为其长度与序列中所有元素的最大公约数的乘积,即 W(L,R)=(RL+1)×gcd(Al,...,Ar)W(L,R) = (R-L+1) × \gcd (A_l,...,A_r)

JYY 希望找出权值最大的子序列。

输入格式

输入一行包含一个正整数 NN

接下来一行,包含 NN 个正整数,表示序列 AiA_i

输出格式

输出文件包含一行一个正整数,表示权值最大的子序列的权值。

输入输出样例 #1

输入 #1

5
30 60 20 20 20

输出 #1

80

说明/提示

1Ai1012,1N1000001 \le A_i \le 10^{12}, 1 \le N \le 100000