J1 例题-4 美食宝典的秘密

题目描述

佩奇在秋游的路上发现了一张带着烤肉味的吃货地图，上面记载着一个关于储水的谜题，据说解开它的人就能找到吃货们梦寐以求的美食宝典。

吃货地图上画着一个奇特的图案：在一片平地上矗立着 $n$ 根不同高度的立柱，每根立柱都笔直地竖立在地面上，第 $i$ 根立柱的位置在坐标 $(i,0)$，高度为 $h_i$。

佩奇需要在这些立柱中选择两根，与地面一起围成一个储水的容器。由于重力的作用，水面必须保持水平，而容器的容量就是两根立柱之间能够盛放的水的数量。

你能帮助佩奇找出可以盛放最多水的两根立柱吗？

说明：容器不能倾斜

输入格式

共两行：

第一行一个整数 $n$，表示立柱的数量；

第二行 $n$ 个整数，以空格分隔，表示每根立柱的高度。

输出格式

一行一个整数，表示最大的储水量。

样例输入

9
1 8 6 2 5 4 8 3 7

样例输出

49

样例分析

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

数据范围

对于 $100\%$ 的数据：$2 \le n \le 10^5$，$0 \le h_i \le 10^4$。