隔板与水槽
题号:NC261038
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定一个数轴,数轴上有n个隔板,第i个隔板的高度为a_i,在数轴上的位置为i
定义一个水槽为两个隔板以及中间的区域,水槽的容积为两个隔板的高度中较小的值乘以两个隔板的距离。

现在你需要找出三个隔板,使得其构成两个水槽(位于中间的隔板将被共用),使得两个水槽的容积和最大,求此容积和。

输入描述:

第一行输入一个整数n
 
接下来一行输入n个数,表示 a_i

3 \leq n \leq 5000
1 \leq a_i \leq 1000000000

输出描述:

一行一个整数,表示三个隔板所组成两个水槽的最大容积和。
示例1

输入

复制
5
1 2 3 4 5

输出

复制
8