题目描述

给定一个长度为 $n$ 的数组 $a$。一个子数组的成本定义为该子数组的长度与其两个最小数之和的乘积。

子数组 $a[l..r]$ 是数组 $a$ 的一部分，仅包含位置从 $l$ 到 $r$（含）的元素。

例如，设数组为 $[5, 3, 1, 5, 3]$。考虑子数组 $a[2..4]$，它由元素 $[3, 1, 5]$ 组成。其长度为 $3$，第一最小值为 $1$，第二最小值为 $3$。因此，其成本为 $3 \cdot (1 + 3) = 12$。考虑另一个子数组 $a[1..2]$，由元素 $[5, 3]$ 组成。其长度为 $2$，第一最小值为 $3$，第二最小值为 $5$。因此，其成本为 $2 \cdot (3 + 5) = 16$。

注意，如果最小数出现多次，则会被多次计算。例如，如果有一个子数组 $[3, 1, 1]$，其长度为 $3$，第一最小值为 $1$，第二最小值为 $1$。因此，其成本为 $3 \cdot (1 + 1) = 6$。

你的任务是找出所有长度至少为两个元素的子数组中的最大成本。也就是说，你需要找出所有子数组 $a[l..r]$（其中 $(1 \leq l < r \leq n)$）的最大成本。

输入格式

• 第一行包含一个整数 $n$（$2 \le n \le 10^6$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

输出格式

输出一个整数——问题的答案。

5
5 3 1 5 3

20

7
1 1 3 5 10 77 5

174

3
1 2 3

10

提示

在第一个示例中，最大成本由子数组 $a[1..5]$ 达到，其长度为 $5$，最小值为 $1$ 和 $3$，乘积 $(1+3) \cdot 5 = 20$。

在第二个示例中，最大成本由子数组 $a[5..6]$ 达到，其长度为 $2$，最小值为 $10$ 和 $77$，乘积 $(10+77) \cdot 2=174$。

在第三个示例中，最大成本由子数组 $a[2..3]$ 达到，其长度为 $2$，最小值为 $2$ 和 $3$，乘积 $(2+3) \cdot 2=10$。

评分细则

• （$6$ 分）：$2 \le n \le 800$
• （$7$ 分）：$2 \le n \le 5\,000$
• （$10$ 分）：$2 \le n \le 20\,000$
• （$24$ 分）：所有测试用例按以下方式随机生成：首先确定一个数字 $n$（非随机），然后每个 $a_i$（$1 \le i \le n$）被赋予 $1$ 到 $10^9$ 之间的值，每个值等概率出现。$2 \le n \le 10^5$。
• （$17$ 分）：$2 \le a_i \le \sqrt{n}$
• （$36$ 分）：无额外限制。

翻译由 DeepSeek V3 完成