A workshop has n vertical planks in a row, the i-th with non-negative height h[i]; consecutive planks are spaced one unit apart. Choosing two planks i < j, you can form a water tank whose two sides are those planks; the tank holds water up to the shorter of the two chosen planks, so the amount it holds equals min(h[i], h[j]) * (j - i) (the horizontal distance times the limiting height). Report the maximum amount any pair of planks can hold.
Input format
Line 1: an integer n.
Line 2: n space-separated non-negative integers, the plank heights left to right.
Output format
A single integer: the maximum water area achievable by any pair of planks.
Constraints
- 2 ≤ n ≤ 100000
- 0 ≤ h[i] ≤ 1000000000