Given an array of length . 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 is a part of the array that includes only the elements located at positions from to , inclusive.
For example, let the array be [5, 3, 1, 5, 3]. Let us consider the subarray , which consists of elements () [3, 1, 5]. Its length is , its first minimum is , and its second minimum is . Therefore, its cost is 3 \cdot (1 + 3) = 12. Let us consider another subarray, , consisting of elements () . Its length is , its first minimum is , and its second minimum is . 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 , its first minimum is , and its second minimum is . 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 , where (1 \leq l < r \leq n).
The first line contains a single integer (2 \le n \le 10^6).
The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^9).
Output a single integer – the answer to the problem.
Example 1
Example 2
Example 3
In the first example, the maximum cost is achieved for the subarray , its length is , its minimums are and , and the product of (1+3) \cdot 5 = 20.
In the second example, the maximum cost is achieved for the subarray , its length is , its minimums are and , and the product of (10+77) \cdot 2=174.
In the third example, the maximum cost is achieved for the subarray , its length is , its minimums are and , and the product of (2+3) \cdot 2=10.
( points): 2 \le n \le 800
( points): 2 \le n \le 5\,000
( points): 2 \le n \le 20\,000
( points): All tests are generated randomly in the following way: first, a number is determined, which does not happen randomly, and then each a_i (1 \le i \le n ) is assigned a value from to 10^9 inclusively with equal probability for each value. 2 \le n \le 10^5.
( points): 2 \le a_i \le \sqrt{n}
( points): No additional constraints.