EOJ Monthly 2018.1

E. 没用的函数

单点时限: 2.0 sec

内存限制: 512 MB

背景故事:出题人当然是希望出的题目看起来并非毫无意义,于是想方设法给题目配上一些背景故事,使得它看起来不那么无趣。但有时候适得其反,比如当你读到这道一看就是套路的题时,很可能就会感到索然无味。

对于一个长度为 n 的数列 a1,a2,,an,求 max1lrnf(l,r), 其中 f(l,r)=|gcd(al,al+1,,ar)|×(al+al+1++ar)

输入格式

第一行一个整数 n(1n106)
第二行 n 个数,分别表示 a1,a2,,an,其中 |ai|106

输出格式

在一行中输出答案。

样例

Input
5
10 20 10 -10 20
Output
500
Input
4
12 0 12 -12
Output
288