Description
给定一个长度为 N 的整数序列 A 。
对于其中任意一段连续的区间 [l,r],定义其权值 val1(l,r) 为其长度与区间最小值的乘
积,val2(l,r) 为其长度与区间最大公约数的乘积。
即:
val1(l,r)=(r−l+1)×min(Al,Al+1,Al+2,...,Ar−1,Ar)
val2(l,r)=(r−l+1)×gcd(Al,Al+1,Al+2,...,Ar−1,Ar)
求出整个序列权值 val1 最大的一段区间或权值 val2 最大的一段区间。
第一行输入问题类型opt,opt=1 表示求权值 val1 最大的一段区间, opt=2 表示求权值
val2 最大的一段区间。
第二行输入一个整数 N(1⩽N⩽1000000),表示序列的长度。
接下来一行,包含 N 个整数,表示序列 A 。
Output
输出一行包含一个正整数,opt=1 表示 val1 最大的子序列的权值,opt=2 表示 val2 最大的子序列的权值。
Samples
1
5
2 3 3 3 3
12
2
8
19 13 23 39 45 4 15 28
45
Limitation
对于 10 的数据,N⩽100 。
对于 30 的数据,N⩽2000 。
对于 60 的数据,N⩽100000。
对于另外 20 的数据,opt=1,Ai 的取值不超过 20 种。
对于 100 的数据, N⩽1000000 , 1⩽Ai⩽1012 。
数据保证 opt=1,opt=2 各占 50。
Tips
建议使用快读