Container With Most Water

Given n non-negative integers representing heights of vertical lines at positions 0 to n-1, find two lines that together with the x-axis form a container that holds the most water. Use two pointers from both ends, moving the shorter one inward. Area = min(height[left], height[right]) * (right - left) Example: [1,8,6,2,5,4,8,3,7] → Max area = 49 (between positions 1 and 8)

Input

Line 1: n. Line 2: n space-separated integers (heights).

Output

The maximum area.

Sample

9
1 8 6 2 5 4 8 3 7

Expected

49