U224231 环路运输

在一条环形公路旁均匀地分布着 $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)$。 求在哪两座仓库之间运送货物需要的代价最大。

第一行包含一个整数 $N$。 第二行包含 $N$ 个整数 $A_1∼A_N$。

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

$2\le N \le 10^6$，$1\le A_i \le 10^7$。