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

Input

5
1 2 3 4 5

Output

6

Explanation

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