题目描述

给你 $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}$)。

输入输出样例

9
1 8 6 2 5 4 8 3 7

49

2
1 1

1

5
4 3 2 1 4

16

3
1 2 1

2

说明/提示

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