There are n vertical support walls standing in a row at positions 0..n-1. Wall i has height h[i]. Choosing two walls i < j and joining them with a flat floor creates a tank whose capacity is (j - i) * min(h[i], h[j]) (the water cannot rise above the shorter of the two chosen walls). Find the maximum possible capacity over all choices of two walls.
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 tank capacity (j - i) * min(h[i], h[j]) over all i < j.
Constraints
- 2 ≤ n ≤ 100000
- 0 ≤ h[i] ≤ 100000