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[\mathrm{2..4}]$, which consists of elements ($a[\mathrm{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[\mathrm{1..2}]$, consisting of elements ($a[\mathrm{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\le l<r\le n)$.

Input

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

Output a single integer – the answer to the problem.

Examples

Note

In the first example, the maximum cost is achieved for the subarray $a[\mathrm{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[\mathrm{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[\mathrm{2..3}]$, its length is $2$, its minimums are $2$ and $3$, and the product of $(2+3)\cdot 2=10$.

Scoring

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

2. ($7$ points): $2\le n\le 5000$

3. ($10$ points): $2\le n\le 20000$

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

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

6. ($36$ points): No additional constraints.