Along a straight canal there are n pillars at positions 1..n, each with a given height. Choosing any two DISTINCT pillars i and j (i < j) and building a wall of water between them, the basin between them can hold exactly (j - i) * min(height[i], height[j]) units of water (bounded by the shorter of the two pillars; the heights of pillars strictly between i and j do not matter). Find the MAXIMUM possible basin capacity over all pairs of pillars.
Input format
Line 1: an integer n (n >= 2).
Line 2: n space-separated non-negative integers, the pillar heights.
Output format
A single integer: the maximum basin capacity achievable over all pairs of pillars.
Constraints
- 2 <= n <= 100000
- 0 <= height <= 1000000