题目描述

给定一个长度为 $n$ 的整数数组 $height$。有 $n$ 条垂线，第 $i$ 条线的两个端点是 $(i, 0)$ 和 $(i, height[i])$。

找出其中的两条线，使得它们与 $x$ 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

输入格式

第一行是整数 $n$ $(0 < n \leq 100,000)$，表示有 $n$ 个整数。

第二行是 $n$ 个整数。整数的范围是在 $0$ 到 $10^4$ 之间。

输出格式

返回容器可以储存的最大水量。

样例

样例输入 #1

9
1 8 6 2 5 4 8 3 7

样例输出 #1

49

数据范围与提示

$0 < n \leq 100,000$,

$0 \leq height[i] \leq 10,000$。