0805算法入门(2)中期测试

P4. 容器

描述

给你 $n$ 个非负整数 $a_1，a_2，\dots，a_n$ ，每个数代表坐标中的一个点 $(i, a_i)$ 。在坐标内画 $n$ 条垂直线，垂直线 $i$ 的两个端点分别为 $(i, a_i)$ 和 $(i, 0)$ 。找出其中的两条线，使得它们与 $x$ 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

输入

第一行一个数字 $n$

接下来 $n$ 个数字 $a_i$

输出

最大面积

样例

输入

9
1 8 6 2 5 4 8 3 7

输出

输入

2
1 1

输出

输入

5
4 3 2 1 4

输出

提示

30%数据： $2 \leq n \leq 100$ ;

100%数据： $n\leq 10^6$ , $0 \leq height[i] \leq 10^4$ ;

提交

题目参数

时间限制	1 秒
内存限制	128 MB

提交