Subarray Cost

문제

Given an array $AA$ of length $NN$, a subarray $A[l\dots r]A[l\; \backslash ldots\; r]$ is defined as the part of the array $AA$ that includes only the elements located at positions from $ll$ to $rr$ inclusively. The cost of a subarray is defined as the product of the length of the subarray and the sum of its two smallest elements.

For example, let the array be $A=[5,1,3,5,3]A\; =\; [5,\; 1,\; 3,\; 5,\; 3]$. Let us consider the subarray $A[2\dots 4]=[1,3,5]A[2\; \backslash ldots\; 4]\; =\; [1,\; 3,\; 5]$. Its length is $33$, its smallest element is $11$, and its second smallest element is $33$. Therefore, its cost is $3\cdot (1+3)=123\; \backslash cdot\; (1\; +\; 3)\; =\; 12$. Let us consider another subarray, $A[1\dots 2]=[5,1]A[1\; \backslash ldots\; 2]\; =\; [5,\; 1]$. Its length is $22$, its smallest element is $11$, and its second smallest element is $55$. Therefore, its cost is $2\cdot (1+5)=122\; \backslash cdot\; (1\; +\; 5)\; =\; 12$.

Note that if the minimal value occurs more than once in a subarray, it is counted several times. For example, the length of the subarray $A[3\dots 5]=[3,5,3]A[3\; \backslash ldots\; 5]\; =\; [3,\; 5,\; 3]$ is $33$, its smallest element is $33$, and its second smallest element is also $33$. Therefore, its cost is $3\cdot (3+3)=183\; \backslash cdot\; (3\; +\; 3)\; =\; 18$.

Given an array, find the maximum cost over all subarrays of at least two elements. That is, you need to find the maximum cost over all subarrays $A[l\dots r]A[l\; \backslash ldots\; r]$, where .

입력

The first line contains $NN$ ($2\le N\le {10}^{6}2\; \backslash le\; N\; \backslash le\; 10^6$), the length of the array. The second line contains $NN$ integers $A_1,A_2,\dots ,A_{N}A\_1,\; A\_2,\; \backslash dots,\; A\_N$ ($1\le A_i\le {10}^{9}1\; \backslash le\; A\_i\; \backslash le\; 10^9$).

출력

Output a single integer, the maximum cost over all subarrays of at least two elements.