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

P4. 容器

Description

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

说明：你不能倾斜容器。

Input

第一行一个数字 $n$

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

Output

最大面积

Examples

Input

9
1 8 6 2 5 4 8 3 7

Output

Input

2
1 1

Output

Input

5
4 3 2 1 4

Output

Hint

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

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

Submit

题目参数

Time Limit	1 second
Memory Limit	128 MB

Submit