100720 - 桶理论

时间限制

1000 毫秒

内存限制

128 MB

通过次数

7

提交次数

9

桶理论是说桶能装的水的高度取决于最短的那块板。我们的问题要更简化一些———这个桶只有两块板。有一组nn块模板,其高度依次为h[i]h[i],没两块之间距离为11。求,用哪两块板作为边缘能装最多的水?

注意:不得移动板的位置,也不得倾斜。

例如,板高依次为1,8,6,2,5,4,8,3,7时,最多能容纳水49:

输入

第一行,一个整数nn,表示模板块数。 接下来nn行,每行一个h[i]h[i],依次表示从左向右每块板的高度。

对于100%的数据:

2n1062 \le n \le 10^6

0h[i]1030 \le h[i] \le 10^3

输出

一个正整数,表示最多能容纳的水。

样例

输入
复制

2
1
1

输出
复制

1

输入
复制

9
1
8
6
2
5
4
8
3
7

输出
复制

49