Container With Most Water

Medium#arrays #two-pointers #greedy· solved by 0 · time limit 2.0 s

Vertical lines of heights $h_1 \dots h_n$ stand at positions $1 \dots n$ . Two lines and the x-axis form a container holding $(j-i) \cdot \min(h_i, h_j)$ water. Find the maximum.

Input

$n$ , then $n$ heights.

Output

The maximum amount of water.

Constraints

$2 \le n \le 10^5$ , $0 \le h_i \le 10^4$

Sample 1

Input

9
1 8 6 2 5 4 8 3 7

Output