Product#11375

Product

2 seconds

256 megabytes

Very hard

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

A subarray $a [l .. r]$ is a part of array $a$ , considering only the numbers at positions from $l$ to $r$ inclusive.

For example, let the array be $[5, 3, 1, 5, 3]$ [5, 3, 1, 5, 3]. Consider the subarray $a [2..4]$ , with elements ( $a [2..4]$ ) — $[3, 1, 5]$ [3, 1, 5]. Its length is $3$ , the first minimum is $1$ , the second minimum is $3$ . Therefore, its cost is $3 \cdot (1 + 3) = 12$ 3 \cdot (1 + 3) = 12. Consider another subarray $a [1..2]$ , with elements ( $a [1..2]$ ) — $[5, 3]$ . Its length is $2$ , the first minimum is $3$ , the second minimum is $5$ . Therefore, its cost is $2 \cdot (3 + 5) = 16$ 2 \cdot (3 + 5) = 16.

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

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

Input

The first line contains one integer $n$ $(2 \leq n \leq 1 0^{6})$ (2 \le n \le 10^6).

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n $(1 \leq a_{i} \leq 1 0^{9})$ (1 \le a_i \le 10^9).

Output

Print one integer — the answer to the problem.

Examples

Example 1

Example 2

Example 3

Note

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

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

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

Scoring

$6$ points: $2 \leq n \leq 800$ 2 \le n \le 800
$7$ points: $2 \leq n \leq 5000$ 2 \le n \le 5\,000
$10$ points: $2 \leq n \leq 20000$ 2 \le n \le 20\,000
$24$ points: All tests are generated randomly as follows: first the number $n$ is determined (not randomly), then for each $a_{i}$ a_i where $1 \leq i \leq n$ 1 \le i \le n, a value from $1$ to $1 0^{9}$ 10^9 inclusive is assigned with equal probability for each value. $2 \leq n \leq 1 0^{5}$ 2 \le n \le 10^5.
$17$ points: $2 \leq a_{i} \leq n$ 2 \le a_i \le \sqrt{n}
$36$ points: No additional constraints