2834: 5501 环路运输
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
在一条环形公路旁均匀地分布着N座仓库，编号为1~N，编号为 i 的仓库与编号为 j 的仓库之间的距离定义为 dist(i,j)=min(|i-j|,N-|i-j|)，也就是逆时针或顺时针从 i 到 j 中较近的一种。每座仓库都存有货物，其中编号为 i 的仓库库存量为 A_i。在 i 和 j 两座仓库之间运送货物需要的代价为 A_i+A_j+dist(i,j)。求在哪两座仓库之间运送货物需要的代价最大。1≤N≤10^6，1<=Ai<=10^7。
Input
第一行一个整数N，第二行N个整数A1~AN
Output
一个整数，表示最大代价。
Sample Input Copy
5
1 8 6 2 5Sample Output Copy
15