C-mex和gcd的乘积_牛客小白月赛79

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

曾经的A，为何如今沦落成了C
——来自一场连续出三个妙妙签到题的良心出题人

给你一个长度为 $n$ 的数列。求这个数列中连续区间的 $\operatorname{mex}$ 乘 $\operatorname{gcd}$ 的最大值是多少？

形式化的：定义 $f(l,r)=\operatorname{mex}(a_l,...,a_r)\times \operatorname{gcd}(a_l,...,a_r)\ ,\ l\le r$ 。求 $f(l,r)_{max}$

关于 $\operatorname{mex}$ ：区间的 $\operatorname{mex}$ 被定义为区间中未出现的最小的非负整数，例如：

$[2,2,1]$ 的 $\operatorname{mex}$ 是 $0$ ，因为 $0$ 不在这个区间中

$[3,1,0,1]$ 的 $\operatorname{mex}$ 是 $2$ ，因为 $0$ , $1$ 在这个区间中，而 $2$ 不在这个数组中

$[0,3,1,2]$ 的 $\operatorname{mex}$ 是 $4$ ，因为 $0$ , $1$ , $2$ , $3$ 在这个区间中，而 $4$ 不在这个数组中

关于 $\operatorname{gcd}$ ：连续区间的最大公约数是指一个数列中相邻的若干个数字的最大公约数，同时也是最大能被区间中所有数整除的数。特殊的，对于任意非负整数 $x$ ， $\operatorname{gcd}(0,x)=x$ ， $\operatorname{gcd}(x)=x$ ，例如：

$\operatorname{gcd}(6,4,3)=\operatorname{gcd}(\operatorname{gcd}(6,4),3)=\operatorname{gcd}(2,3)=1$

$\operatorname{gcd}(5,2,0)=\operatorname{gcd}(\operatorname{gcd}(5,2),0)=\operatorname{gcd}(1,0)=1$

$\operatorname{gcd}(5)=5$

输入描述:

第一行包含一个整数，表示数列的长度
第二行包含个非负整数，表示该数列

输出描述:

输出一个整数，表示数列中连续区间的乘的最大值

示例1

输入

复制

5
0 1 2 1 4

输出

复制

说明

选择区间，此时，取得最大值。区间同样也能取到最大值

示例2

输入

复制

3
0 1 0

输出

复制

说明

选择区间，此时，取得最大值。区间和同样也能取到最大值