Problem G
Tom Sawyering

You just finished reading the great American novel Tom Sawyer, and now you’re feeling inspired. You really want to build a fence, and conveniently, in your backyard you have a line of evenly-spaced fence posts of varying sizes. However, you want to build as big of a fence as possible (by surface area) so you can paint it just like Tom didn’t (you didn’t read the book very closely).

Later today you’re going to go shopping for a large, singular piece of plywood to act as your fence and this piece of wood is going to lie between two of the fence posts. Its area is going to be equal to the shorter of the end posts multiplied by the distance between the posts. Your job is to figure out the largest possible piece of plywood that can be purchased given the posts in your backyard.

Input

The input consists of two lines. The first line is an integer, $n$ ($2 \le n \le 1\, 000\, 000$), which represents the number of posts. The second line consists of $n$ integers, $x_1$-$x_ n$ ($1 \le x_ i \le 10\, 000$), which represent the heights of the posts in feet. All of the posts are exactly one foot apart and their width is negligible.

Output

Your job is to output the largest possible area of a piece of plywood that can be placed using two of the posts above.

6
1 6 2 4 9 3

18