题目描述

小due梦想做个泥瓦匠,为了磨练技艺,他在家里立了很多面墙,这些墙排列成了一个长度为n的整数数组。理想情况下,墙面完全垂直于地面,第i个墙面的两个端点是(i,0)和(i, height[i])。现在小due想要找出其中两个墙面,使得他们与地面(x轴)共同构成的蓄水池可以容纳最多的水。墙的长度都相同。


输入格式

两行,第一行为n,第二行为从左到右墙的高度。


输出格式

返回该蓄水池可以存储的最大水量。(仅需计算平面面积即可)


样例数据

输入

9
1 8 6 2 5 4 8 3 7

输出

49

备注

$2 \leq n = height.length \leq 10^5$
$0 \leq height[i] \leq 10^4$

样例解释:
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

题解