P15059 [UOI 2023 II Stage] Product

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.

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.