题目内容

在平面直角坐标系中放置着 $n$ 条竖直的线段。第 $i$ 条线段的下端位于 $(i, 0)$，上端位于 $(i, height[i])$，其中 $height$ 是一个长度为 $n$ 的整数数组。

任选两条线段，它们与这两条线段之间的 $x$ 轴部分可以围成一个容器。容器能够储存的水量，等于两条线段中较短一条的高度乘以它们之间的水平距离。

请找出所有两两组合中能够储存的最大水量，并输出该最大值。

容器在盛水时不能倾斜。

约束条件：

• 数组 $height$ 的长度为 $n$，满足 $2 \le n \le 10^5$。
• 对于每个下标 $i$，$0 \le height[i] \le 10^4$。

输入描述

第一行包含一个整数 $n$，表示数组 $height$ 的长度。

第二行包含 $n$ 个整数，依次表示数组 $height$ 中的元素。

输出描述

输出一个整数，表示容器能够储存的最大水量。

样例1

输入

9
1 8 6 2 5 4 8 3 7

输出

49

说明

选择第 2 条线段和第 9 条线段。

它们的高度分别为 8 和 7，水平距离为 $9 - 2 = 7$。容器高度由较短的线段决定，即 $\min(8, 7) = 7$，因此水量为 $7 \times 7 = 49$。

其他组合的水量均不超过该值，所以最大水量为 49。

样例2

输入

2
0 5

输出

0

说明

只有第 1 条和第 2 条线段这一种组合。

两条线段的高度分别为 0 和 5，较短高度为 $\min(0, 5) = 0$，水平距离为 $1$，所以水量为 $0 \times 1 = 0$。

这个样例同时覆盖了最小长度 $n = 2$ 和高度为 0 的边界情况。

样例3

输入

5
4 3 2 1 4

输出

16

说明

选择第 1 条线段和第 5 条线段。

它们的高度都为 4，水平距离为 $5 - 1 = 4$。容器高度为 $\min(4, 4) = 4$，因此水量为 $4 \times 4 = 16$。

其他组合能够形成的水量均不超过 16，所以最大值为 16。