Description

给定一个长度为 $N$ 的整数序列 $A$ 。

对于其中任意一段连续的区间 $[l,r]$,定义其权值 $val1(l, r)$ 为其长度与区间最小值的乘 积，$val2(l, r)$ 为其长度与区间最大公约数的乘积。 即：

$val1(l, r) = (r − l + 1) × min(A_{l}, A_{l+1}, A_{l+2}, . . . , A_{r−1}, A_{r})$

$val2(l, r) = (r − l + 1) × gcd(A_{l}, A_{l+1}, A_{l+2}, . . . , A_{r−1}, A_{r})$

求出整个序列权值 $val1$ 最大的一段区间或权值 $val2$ 最大的一段区间。

Format

Input

第一行输入问题类型$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 , A_{i}$ 的取值不超过 $20$ 种。

对于 $100$ 的数据, $N ⩽ 1000000$ , $1 ⩽ A_{i} ⩽ 10^{12}$ 。

数据保证 $opt = 1, opt = 2$ 各占 $50$。

Tips

建议使用快读