Circus 2

Long before he became a goat, Andy was pursuing a career in academia. After writing that $17$ is a composite number on an exam, Andy decided that if he was going to be a clown anyway, he may as well join the circus. Andy is once again in charge of setting up the tightropes.

There are $n$ posts in a line, where the $i$th post has height $a_i$. Andy must choose exactly two posts. The height of the tightrope is the minimum of the two chosen post heights, and the distance between posts $i$ and $j$ is $|i - j|$.

If Andy chooses posts $i$ and $j$, the audience's excitement factor is $|i - j| \cdot \min(a_i, a_j)$. Find the maximum possible excitement factor.

Input

The first line contains an integer $n$, the number of posts.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, where $a_i$ is the height of the $i$th post.

Output

Print a single integer: the maximum excitement factor Andy can achieve.

Constraints

• $2 \le n \le 2 \cdot 10^5$
• $1 \le a_i \le 10^9$

Example 1

5
1 2 3 4 5

6

Explanation

Choosing the $3$rd and $5$th posts gives excitement factor $|5 - 3| \cdot \min(3, 5) = 2 \cdot 3 = 6$.