Container With Most Water

Problem statement

Fence posts stand one unit apart, with heights given in an array. Choose two posts to form the sides of a rectangular water container. Its capacity is the distance between the posts multiplied by the shorter height. Find the greatest capacity without tilting the container.

Input format

First line: n. Second line: n space-separated integers.

Output format

Print the maximum capacity.

Constraints

2 <= n <= 100000; 0 <= height <= 1000000000; use 64-bit arithmetic.

Sample input

5
4 1 3 2 5

Sample output

16