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 . Let us consider the subarray , which consists of elements () . Its length is , its first minimum is , and its second minimum is . Therefore, its cost is . Let us consider another subarray, , consisting of elements () . Its length is , its first minimum is , and its second minimum is . Therefore, its cost is .
Note that if the minimum number occurs more than once, it is counted several times. For example, if there is a subarray , its length is , its first minimum is , and its second minimum is . Therefore, its cost is .
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 .
输入格式
The first line contains a single integer .
The second line contains integers .
输出格式
Output a single integer -- the answer to the problem.
样例
样例输入 1
5
5 3 1 5 3
样例输出 1
20
样例输入 2
7
1 1 3 5 10 77 5
样例输出 2
174
样例输入 3
3
1 2 3
样例输出 3
10
数据范围与提示
In the first example, the maximum cost is achieved for the subarray , its length is , its minimums are and , and the product of .
In the second example, the maximum cost is achieved for the subarray , its length is , its minimums are and , and the product of .
In the third example, the maximum cost is achieved for the subarray , its length is , its minimums are and , and the product of .
Scoring
( points):
( points):
( points):
( points): All tests are generated randomly in the following way: first, a number is determined, which does not happen randomly, and then each ( ) is assigned a value from to inclusively with equal probability for each value. .
