题目描述

为了和她的姐妹们并肩而立，Yana 今年也要给你出一道题。经过长时间思考之后，她决定给出下面这道正合你口味的题目：

给定一个正整数序列 a_1,a_2,...,a_N。你可以任选一段区间 1 ≤ l ≤ r ≤ N，并计算它的值：

$$(r-l+1) \times \gcd(a_l,a_{l+1},...,a_r)$$

其中 gcd(a_l,a_{l+1},...,a_r) 表示从位置 l 到位置 r 这段数字的最大公约数。

你需要求出该值的最大可能值。形式化地：

$$\max_{l=1}^{N} \max_{r=l}^{N} (r-l+1) \times \gcd(a_l,a_{l+1},...,a_r)$$

任务要求

请编写程序 segment，实现函数 max_segment，它将与评测程序一起编译，并求出：

$$\max_{l=1}^{N} \max_{r=l}^{N} (r-l+1) \times \gcd(a_l,a_{l+1},...,a_r)$$

实现细节

你需要实现如下函数：

long long max_segment(std::vector<int> A)

该函数只会被评测程序调用一次，参数即为整个序列 A。

你的程序文件 segment.cpp 必须实现函数 max_segment。程序中可以包含其他为实现所需的代码和函数，但不得包含主函数 main。

同时，你不得从标准输入读取数据，也不得向标准输出输出任何内容。

你的程序必须通过如下预处理指令包含头文件 segment.h：

#include "segment.h"

数据范围与评分

• 1 ≤ N ≤ 3 × 10^6
• 1 ≤ A_i ≤ 2 × 10^9

样例 #1

输入 #1

7
6 5 10 15 2 4 8

输出 #1

15

说明 #1

答案在 l = 2, r = 4 时取得。

样例 #2

输入 #2

7
2 2 3 7 5 5 5

输出 #2

15

说明 #2

答案在 l = 5, r = 7 时取得。这个样例满足子任务 4 的限制。

样例 #3

输入 #3

7
2 2 1 4 4 8 2

输出 #3

12

说明 #3

答案在 l = 4, r = 6 时取得。这个样例满足子任务 5 的限制。

本地测试

题目提供了文件 Lgrader.cpp，你可以将它与你的程序一起编译，用于本地测试。

程序运行时，会先从标准输入读取 N，然后读取每一朵花的颜色。随后会输出所进行的通信过程。你可以按需要修改提供的文件。

子任务

子任务	分值	必须通过的子任务	额外限制
1	0	-	仅为题面中的样例
2	3	1	N ≤ 5 × 10^2
3	4	1-2	N ≤ 2 × 10^4
4	6	-	每个 A_i 都是质数
5	16		每个 A_i = 2^{x_i}，其中 x_i 为非负整数
6	21	1-3	N ≤ 7 × 10^4
7	20	1-3, 6	N ≤ 5 × 10^5
8	30	1-7	无

只有当某个子任务的全部测试通过后，才能获得该子任务的分数。