luogu#P10957. 环路运输

环路运输

题目描述

在一条环形公路旁均匀地分布着 NN 座仓库,编号为 1N1 \sim N,编号为 ii 的仓库与编号为 jj 的仓库之间的距离定义为 dist(i,j)=min(ij,Nij)dist(i,j)=\min⁡(|i-j|,N-|i-j|),也就是逆时针或顺时针从 iijj 中较近的一种。

每座仓库都存有货物,其中编号为 ii 的仓库库存量为 AiA_i

iijj 两座仓库之间运送货物需要的代价为 Ai+Aj+dist(i,j)A_i+A_j+dist(i,j)

求在哪两座仓库之间运送货物需要的代价最大。

输入格式

第一行包含一个整数 NN

第二行包含 NN 个整数 A1ANA_1 \sim A_N

输出格式

输出一个整数,表示最大代价。

5
1 8 6 2 5
15

提示

数据保证,2N1062 \le N \le 10^61Ai1071 \le A_i \le 10^7