Maximum Water Storage

Problem Description

You are given $n$ non-negative integers $a_1, a_2, \dots, a_n$. Each integer represents a point $(i, a_i)$ in the Cartesian plane.

We can now draw $n$ vertical line segments, where the $i$-th segment has endpoints $(i, a_i)$ and $(i, 0)$.

Among these $n$ segments, find two that, together with the $x$-axis, form the sides of a container such that the container can hold the maximum amount of water. Note that you may not tilt the container.

Input Format

A non-negative integer $n\ (1 < n \le 10^5)$, followed by the $n$ integers in succession.

Output Format

The maximum amount of water the container can hold, as an integer (not exceeding $10^{18}$).

Sample Input 1

9
1 8 6 2 5 4 8 3 7

Sample Output 1

49

Sample Input 2

2
1 1

Sample Output 2

1

Sample Input 3

5
4 3 2 1 4

Sample Output 3

16

Sample Input 4

3
1 2 1

Sample Output 4

2

Hint

Explanation: the vertical lines in the figure represent the input array $[1, 8, 6, 2, 5, 4, 8, 3, 7]$. In this case, the maximum amount of water the container can hold (shown as the blue region) is $49$.