There are n vertical walls standing at positions 0, 1, ..., n-1. Wall i has height heights[i]. Choosing two walls i < j forms a container that holds water up to the shorter of the two walls; the amount of water it can hold equals (j - i) * min(heights[i], heights[j]) (the ground is flat and inner walls do not spill water out through the sides).
Return the maximum amount of water any pair of walls can hold.
Input format
Line 1: an integer n.
Line 2: n space-separated non-negative integers, the wall heights.
Output format
A single integer: the maximum area, or 0 if fewer than two positive-width containers exist.
Constraints
- 2 ≤ n ≤ 100000
- 0 ≤ heights[i] ≤ 1000000000