最大存水量

题目描述

给你 $n$ 个非负整数 $a_1, a_2,\dots, a_n$。每个整数表示平面直角坐标系中的一个点 $(i,a_i)$。

现在我们可以画出 $n$ 条垂直线段，其中第 $i$ 条线段的两个端点分别为 ($i, a_i$) 和 $(i,0)$。

请你在这 $n$ 条线段中找出两条，使其与 $x$ 轴构成一个容器的侧面图，使得该容器能保存最大容量的水。注意你不能使容器倾斜。

输入格式

输入包含一个非负整数 $n(1\lt n\le 10^5)$，接着连续输入 $n$ 个整数。

输出格式

输出容器的最大存水量，为一个整数(不超过 $10^{18}$)。

样例输入 1

9
1 8 6 2 5 4 8 3 7

样例输出 1

49

样例输入 2

2
1 1

样例输出 2

1

样例输入 3

5
4 3 2 1 4

样例输出 3

16

样例输入 4

3
1 2 1

样例输出 4

2

提示

解释：图中垂直线代表输入数组 $[1,8,6,2,5,4,8,3,7]$。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。