Product#191

Product

2 secondes
256 mégaoctets
Hard

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).

Input

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

Output a single integer – the answer to the problem.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

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.

Scoring

  1. ( points): 2 \le n \le 800

  2. ( points): 2 \le n \le 5\,000

  3. ( points): 2 \le n \le 20\,000

  4. ( 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.

  5. ( points): 2 \le a_i \le \sqrt{n}

  6. ( points): No additional constraints.