1445: 容积和

雨母楼顶有一个有 $n$ 块板砖，第 $i$ 块板砖的高度为 $a_i$ , 在楼顶中的位置为 $i$。

中间没有其他板砖的两块板砖能够形成一个容器，假定两块板砖是第 $i,j$ 块，那么他们的容积为 $min(a_i,a_j)*|i-j|$

现在你需要撤走 $n-3$ 块板砖，使得雨母楼顶剩下的板砖形成两个容器，求这两个容器的最大容积和。

第一行输入一个整数 $n$。

第二行，包含 $n$ 个整数 $a_i$，为 $n$ 块板砖的高度。

数据范围:  
$10\%$的数据满足：$3 \leq n \leq 10,1 \leq a_i \leq 10^5$   
$60\%$的数据满足：$3 \leq n \leq 300,1 \leq a_i \leq 10^5$   
$100\%$的数据满足：$3 \leq n \leq 6000,1 \leq a_i \leq 10^9$ 

输出一个整数，表示最大容积和。

5
4 1 6 4 3

15

样例中，留下第$1，4，5$块板砖。

答案为$min(4,4)*|4-1|+min(3,4)*|5-4|=15$。