题目描述

Given an array $a$ of length $n$. The cost of a subarray is defined as the product of the length of the subarray and the sum of its two smallest numbers.

A subarray $a[l..r]$ is a part of the array $a$ that includes only the elements located at positions from $l$ to $r$, inclusive.

For example, let the array be $[5, 3, 1, 5, 3]$. Let us consider the subarray $a[2..4]$, which consists of elements ($a[2..4]$) $[3, 1, 5]$. Its length is $3$, its first minimum is $1$, and its second minimum is $3$. Therefore, its cost is $3 \cdot (1 + 3) = 12$. Let us consider another subarray, $a[1..2]$, consisting of elements ($a[1..2]$) $[5, 3]$. Its length is $2$, its first minimum is $3$, and its second minimum is $5$. Therefore, its cost is $2 \cdot (3 + 5) = 16$.

Note that if the minimum number occurs more than once, it is counted several times. For example, if there is a subarray $[3, 1, 1]$, its length is $3$, its first minimum is $1$, and its second minimum is $1$. Therefore, its cost is $3 \cdot (1 + 1) = 6$.

Your task is to find the maximum cost over all subarrays of length at least two elements. That is, you need to find the maximum cost over all subarrays $a[l..r]$, where $(1 \leq l < r \leq n)$.

输入格式

The first line contains a single integer $n$ $(2 \le n \le 10^6)$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$.

输出格式

Output a single integer -- the answer to the problem.

5
5 3 1 5 3

20

7
1 1 3 5 10 77 5

174

3
1 2 3

10

提示

In the first example, the maximum cost is achieved for the subarray $a[1..5]$, its length is $5$, its minimums are $1$ and $3$, and the product of $(1+3) \cdot 5 = 20$.

In the second example, the maximum cost is achieved for the subarray $a[5..6]$, its length is $2$, its minimums are $10$ and $77$, and the product of $(10+77) \cdot 2=174$.

In the third example, the maximum cost is achieved for the subarray $a[2..3]$, its length is $2$, its minimums are $2$ and $3$, and the product of $(2+3) \cdot 2=10$.

Scoring

• ($6$ points): $2 \le n \le 800$
• ($7$ points): $2 \le n \le 5\,000$
• ($10$ points): $2 \le n \le 20\,000$
• ($24$ points): All tests are generated randomly in the following way: first, a number $n$ is determined, which does not happen randomly, and then each $a_i$ ($1 \le i \le n$ ) is assigned a value from $1$ to $10^9$ inclusively with equal probability for each value. $2 \le n \le 10^5$.
• ($17$ points): $2 \le a_i \le \sqrt{n}$
• ($36$ points): No additional constraints.